Kontextfreie Grammatik < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Aufgabe | Es sei A = {0,1,K} und [mm] L_{1} \subseteq [/mm] A* mit:
[mm] L_{1} [/mm] = { [mm] w_{1}Kw_{2} [/mm] | [mm] w_{1}, w_{2} \in [/mm] {0,1}* [mm] \wedge Num_{2}(R(w_{1})) [/mm] < [mm] Num_{2}(w_{2}) [/mm] }
Dabei bezeichne R(w) das Spiegelbild von w.
Geben Sie eine kontextfreie Grammatik [mm] G_{1} [/mm] an, für die gilt: [mm] L(G_{1}) [/mm] = [mm] L_{1}. [/mm] |
Da [mm] w_{1} [/mm] und [mm] w_{2} [/mm] nicht zwingend die gleiche länge haben, würde ich jetzt erstmal so vorgegangen, beide jeweils gleichmäßig abzubilden, bis die Wortlänge einer der beiden erreicht ist. Denn eine einzige weitere 1 auf der rechten Seite würde dann schon bedeuten, dass [mm] Num_{2}(w_{2}) [/mm] größer wird
X -> 0X0 | 1X0 | 0X1 | 1X1
Jetzt ist man am Scheidepunkt, entweder w1 oder w2 ist das längere Wort. Zunächst einmal betrachte ich |w1| > |w2|, w1 darf also nur noch um 0en erweitert werden, sonst wären die Vorgaben nicht mehr erfüllt:
X -> [mm] 0X_{1}1 [/mm] , [mm] X_{1} [/mm] -> [mm] 0X_{1} [/mm] | K
Dann den Fall |w2| > |w1|, hier wäre zu beachten, dass w2 noch um mindestens eine 1 erweitert werden muss, welche dann letztlich ausschlaggebend ist:
X -> [mm] X_{2}, X_{2} [/mm] -> [mm] X_{2}0 [/mm] | [mm] X_{3}1, X_{3} [/mm] -> K | [mm] X_{2}
[/mm]
Insgesamt also
[mm] L(G_{1}) [/mm] = ( {X,X1,X2,X3},{0,1,K},X, X -> 0X0 | 1X0 | 0X1 | 1X1 | [mm] 0X_{1}1 [/mm] | [mm] X_{2}, X_{1} [/mm] -> [mm] 0X_{1} [/mm] | K, [mm] X_{2} [/mm] -> [mm] X_{2}0 [/mm] | [mm] X_{3}1, X_{3} [/mm] -> K | [mm] X_{2} [/mm] )
Käme das hin?
Danke schonmal
GHoernle
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 20:39 Di 31.08.2010 | | Autor: | felixf |
Moin!
> Es sei A = {0,1,K} und [mm]L_{1} \subseteq[/mm] A* mit:
>
> [mm]L_{1}[/mm]Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
= { [mm]w_{1}Kw_{2}[/mm] | [mm]w_{1}, w_{2} \in[/mm] {0,1}* [mm]\wedge Num_{2}(R(w_{1}))[/mm]
> < [mm]Num_{2}(w_{2})[/mm]Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
}
>
> Dabei bezeichne R(w) das Spiegelbild von w.
Was bedeutet denn $Num_2(w)$?
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 18:44 Mi 01.09.2010 | | Autor: | G-Hoernle |
Sorry, das scheint von meinem prof wohl selbst erfunden zu sein.
Rechnet auf jeden Fall von Dual in Dezimal um :)
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 22:59 Mi 01.09.2010 | | Autor: | felixf |
Moin!
> Es sei A = {0,1,K} und [mm]L_{1} \subseteq[/mm] A* mit:
>
> [mm]L_{1}[/mm]Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
= { [mm]w_{1}Kw_{2}[/mm] | [mm]w_{1}, w_{2} \in[/mm] {0,1}* [mm]\wedge Num_{2}(R(w_{1}))[/mm]
> < [mm]Num_{2}(w_{2})[/mm]Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
}
Also enthaelt $L_1$ u.a. das Wort 01K11, da $R(01) = 10$ kleiner als $11$ ist bzgl. der Binaerdarstellung.
> Da [mm]w_{1}[/mm] und [mm]w_{2}[/mm] nicht zwingend die gleiche länge
> haben, würde ich jetzt erstmal so vorgegangen, beide
> jeweils gleichmäßig abzubilden, bis die Wortlänge einer
> der beiden erreicht ist. Denn eine einzige weitere 1 auf
> der rechten Seite würde dann schon bedeuten, dass
> [mm]Num_{2}(w_{2})[/mm] größer wird
>
> X -> 0X0 | 1X0 | 0X1 | 1X1
>
> Jetzt ist man am Scheidepunkt, entweder w1 oder w2 ist das
> längere Wort. Zunächst einmal betrachte ich |w1| > |w2|,
> w1 darf also nur noch um 0en erweitert werden, sonst wären
> die Vorgaben nicht mehr erfüllt:
>
> X -> [mm]0X_{1}1[/mm] , [mm]X_{1}[/mm] -> [mm]0X_{1}[/mm] | K
>
> Dann den Fall |w2| > |w1|, hier wäre zu beachten, dass w2
> noch um mindestens eine 1 erweitert werden muss, welche
> dann letztlich ausschlaggebend ist:
>
> X -> [mm]X_{2}, X_{2}[/mm] -> [mm]X_{2}0[/mm] | [mm]X_{3}1, X_{3}[/mm] -> K | [mm]X_{2}[/mm]
>
> Insgesamt also
>
> [mm]L(G_{1})[/mm] = ( {X,X1,X2,X3},{0,1,K},X, X -> 0X0 | 1X0 | 0X1 |
> 1X1 | [mm]0X_{1}1[/mm] | [mm]X_{2}, X_{1}[/mm] -> [mm]0X_{1}[/mm] | K, [mm]X_{2}[/mm] -> [mm]X_{2}0[/mm]
> | [mm]X_{3}1, X_{3}[/mm] -> K | [mm]X_{2}[/mm] )
>
> Käme das hin?
Kannst du damit das Wort 01K11 zusammenbekommen? Ich nicht...
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 01:30 Do 02.09.2010 | | Autor: | G-Hoernle |
Mist. Ich werde mich noch einmal dran setzen ...
Ich tue mich damit ein wenig schwer, gibt es da eine art taktik, nach dem man auf die lösung kommt?
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 05:13 Do 02.09.2010 | | Autor: | felixf |
Moin!
> Mist. Ich werde mich noch einmal dran setzen ...
Viel Erfolg!
> Ich tue mich damit ein wenig schwer, gibt es da eine art
> taktik, nach dem man auf die lösung kommt?
Ich wuerd so vorgehen:
Ich ueberlege mir erstmal, wann genau [mm] $Num_2(w_1) [/mm] < [mm] Num_2(w_2)$ [/mm] gilt:
* die hinteren $k$ Stellen sind beliebig
* davor kommt eine Stelle, bei der [mm] $w_1$ [/mm] eine 0 und [mm] $w_2$ [/mm] eine 1 hat, alternativ ist [mm] $w_1$ [/mm] vorbei und bei [mm] $w_2$ [/mm] kommt irgendwas, was irgenwann nochmal eine 1 hat;
* davor sind alle Stellen von [mm] $w_1$ [/mm] und [mm] $w_2$ [/mm] identisch,
* bis [mm] $w_2$ [/mm] vorbei ist und [mm] $w_1$ [/mm] zusaetzlich noch weitere Stellen haben kann;
* natuerlich kann auch [mm] $w_2$ [/mm] laenger sein, aber dann duerfen nur noch Nullen kommen.
Viel Spass beim Basteln!
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 05:16 Do 02.09.2010 | | Autor: | felixf |
Moin!
> > Ich tue mich damit ein wenig schwer, gibt es da eine art
> > taktik, nach dem man auf die lösung kommt?
Ein Zusatz noch: versuch doch mal einen endlichen Automat zu basteln, der der Reihe nach die Stellen von [mm] $w_1$ [/mm] und [mm] $w_2$ [/mm] bekommt (also jeweils die letzten Stellen von beiden, dann die vorletzten, etc.), und der genau dann akzeptieren soll wenn [mm] $Num_2(w_1) [/mm] < [mm] Num_2(w_2)$ [/mm] ist.
Den Automaten kannst du dann recht leicht in die gesuchte Grammatik umschreiben.
LG Felix
|
|
|
| |
|
Ich wage den nächsten Versuch, diesmal mit 6 Nichtterminalsymbolen. Ich habe mir zur Hilfe an die Nichtterminalsymbole dran geschrieben, was gerade größer ist:
[mm] X_{=} [/mm] -> [mm] 0X_{=}0 [/mm] | 1 [mm] X_{=} [/mm] 1 | 0 [mm] X_{<} [/mm] 1 | 1 [mm] X_{>} [/mm] 0 | [mm] X_{>>} [/mm] | [mm] X_{<<}
[/mm]
[mm] X_{<} [/mm] -> [mm] 0X_{<}1 [/mm] | [mm] 1X_{>}0 [/mm] | [mm] 0X_{<}0 [/mm] | [mm] 1X_{<}1 [/mm] | K
[mm] X_{>} [/mm] -> [mm] 1X_{>}0 [/mm] | [mm] 0X_{<}1 [/mm] | [mm] 1X_{>}1 [/mm] | [mm] 0X_{>}0 [/mm] | [mm] X_{>>}
[/mm]
[mm] X_{>>} [/mm] -> [mm] X_{>>}0 [/mm] | Y1
Y -> [mm] X_{>>} [/mm] | K
[mm] X_{<<} [/mm] -> [mm] 0X_{<<} [/mm] | K
Hoffentlich kommts jetzt hin :)
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 21:34 Do 02.09.2010 | | Autor: | felixf |
Moin!
> Ich wage den nächsten Versuch, diesmal mit 6
> Nichtterminalsymbolen. Ich habe mir zur Hilfe an die
> Nichtterminalsymbole dran geschrieben, was gerade größer
> ist:
Sehr gute Idee :)
> [mm]X_{=}[/mm] -> [mm]0X_{=}0[/mm] | 1 [mm]X_{=}[/mm] 1 | 0 [mm]X_{<}[/mm] 1 | 1 [mm]X_{>}[/mm] 0 |
> [mm]X_{>>}[/mm] | [mm]X_{<<}[/mm]
Ich nehme an, [mm] $X_{=}$ [/mm] ist den Startsymbol?
> [mm]X_{<}[/mm] -> [mm]0X_{<}1[/mm] | [mm]1X_{>}0[/mm] | [mm]0X_{<}0[/mm] | [mm]1X_{<}1[/mm] | K
>
> [mm]X_{>}[/mm] -> [mm]1X_{>}0[/mm] | [mm]0X_{<}1[/mm] | [mm]1X_{>}1[/mm] | [mm]0X_{>}0[/mm] | [mm]X_{>>}[/mm]
>
> [mm]X_{>>}[/mm] -> [mm]X_{>>}0[/mm] | Y1
>
> Y -> [mm]X_{>>}[/mm] | K
>
> [mm]X_{<<}[/mm] -> [mm]0X_{<<}[/mm] | K
>
> Hoffentlich kommts jetzt hin :)
Das ist schon wesentlich besser, aber:
Probieren wir mal $00000K1$. Wir fangen mit [mm] $X_{=} \to [/mm] 0 [mm] X_{<} [/mm] 1$ an. Jetzt komm ich aber nicht weiter, ich kann [mm] $X_{<}$ [/mm] nicht durch etwas ersetzen was nicht auch auf die rechte Seite noch irgendwas einfuegt.
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 21:51 Do 02.09.2010 | | Autor: | G-Hoernle |
Argh :) Also noch das dazu
[mm] X_{<} [/mm] -> [mm] X_{<<}
[/mm]
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 21:59 Do 02.09.2010 | | Autor: | felixf |
Moin!
> Argh :) Also noch das dazu
>
> [mm]X_{<}[/mm] -> [mm]X_{<<}[/mm]
Ich hab grad noch ein weiteres Problem entdeckt:
[mm] $X_{=} \to X_{<<} \to [/mm] K$ ergibt ein Wort, was nicht in der Sprache vorkommt. (Schliesslich ist hier [mm] $Num_2(w_1) [/mm] = 0 = [mm] Num_2(w_2)$.)
[/mm]
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 22:10 Do 02.09.2010 | | Autor: | G-Hoernle |
Stimmt, da muss es weg
Zusammenfassend:
$ [mm] X_{=} [/mm] $ -> $ [mm] 0X_{=}0 [/mm] $ | 1 $ [mm] X_{=} [/mm] $ 1 | 0 $ [mm] X_{<} [/mm] $ 1 | 1 $ [mm] X_{>} [/mm] $ 0 | $ [mm] X_{>>} [/mm] $
$ [mm] X_{<} [/mm] $ -> $ [mm] 0X_{<}1 [/mm] $ | $ [mm] 1X_{>}0 [/mm] $ | $ [mm] 0X_{<}0 [/mm] $ | $ [mm] 1X_{<}1 [/mm] $ | K | $ [mm] X_{<<} [/mm] $
$ [mm] X_{>} [/mm] $ -> $ [mm] 1X_{>}0 [/mm] $ | $ [mm] 0X_{<}1 [/mm] $ | $ [mm] 1X_{>}1 [/mm] $ | $ [mm] 0X_{>}0 [/mm] $ | $ [mm] X_{>>} [/mm] $
$ [mm] X_{>>} [/mm] $ -> $ [mm] X_{>>}0 [/mm] $ | Y1
Y -> $ [mm] X_{>>} [/mm] $ | K
$ [mm] X_{<<} [/mm] $ -> $ [mm] 0X_{<<} [/mm] $ | K
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 22:33 Do 02.09.2010 | | Autor: | felixf |
Moin!
> Stimmt, da muss es weg
>
> Zusammenfassend:
>
> [mm]X_{=}[/mm] -> [mm]0X_{=}0[/mm] | 1 [mm]X_{=}[/mm] 1 | 0 [mm]X_{<}[/mm] 1 | 1 [mm]X_{>}[/mm] 0 |
> [mm]X_{>>}[/mm]
>
> [mm]X_{<}[/mm] -> [mm]0X_{<}1[/mm] | [mm]1X_{>}0[/mm] | [mm]0X_{<}0[/mm] | [mm]1X_{<}1[/mm] | K |
> [mm]X_{<<}[/mm]
>
> [mm]X_{>}[/mm] -> [mm]1X_{>}0[/mm] | [mm]0X_{<}1[/mm] | [mm]1X_{>}1[/mm] | [mm]0X_{>}0[/mm] | [mm]X_{>>}[/mm]
>
> [mm]X_{>>}[/mm] -> [mm]X_{>>}0[/mm] | Y1
>
> Y -> [mm]X_{>>}[/mm] | K
Damit ist das Wort $K1$ etwa moeglich, jedoch nicht $K01$. (Einfach $Y [mm] \to [/mm] Y0$ hinzufuegen, und am besten auch $Y [mm] \to [/mm] Y1$ und das $Y [mm] \to X_{>>}$ [/mm] herauswerfen.)
> [mm]X_{<<}[/mm] -> [mm]0X_{<<}[/mm] | K
Hier solltest du auch noch [mm] $X_{<<} [/mm] 0$ hinzufuegen, ansonsten ist z.B. $0K01$ nicht moeglich.
LG Felix
|
|
|
|
