Frage von titan777, 42

Wie lautet die Grammatik zur formalen Sprache L = {0^n 1^n 0^n | n ≥ 0 }?

Meiner Meinung nach müsste "n" ja für alle gleich sein, oder? Wenn ja dann bekomme ich es absolut nicht hin. Wenn nicht dann ist es einfach. Ich danke schon mal im Vorraus für die Hilfe. :)

Antwort
von RakonDark, 24

0^n = 0

1^n = 1

0^n = 0

wenn n >= 0

Der Exponent sagt aus wieviel mal die Zahl mit sich selbst mal genommen wird . Ist n = 0 so bleibt die Zahl als solche stehen und wird gar nicht multipliziert .

Mehr kann ich dazu nicht sagen , da ich es rein Mathematisch sehe .

und bitte frag mich jetzt nicht warum 5^1 = 5 ist :) wir sind ja auch beim Fall 0^n :) Und zum multiplizieren brauchen wir 2 Zahlen also ^2 :)

Kommentar von titan777 ,

Leider nicht die Antwort die ich suche. Bei den formalen Sprachen gibt der Exponent lediglich an wie oft der jeweilige Buchstabe im Wort vorkommen muss. Statt der 0 und der 1 könnte ich an der Stelle auch ein a und ein b haben, was mathematisch ja dann nicht mehr geht.

Trotzdem Danke :)

Kommentar von RakonDark ,

Das hab ich mir schon fast gedacht :) Dann ist es eine gar nicht Hilfreiche antwort ;)

Antwort
von Schachpapa, 12

Ich versuch's mal (ist fast 30 Jahre her):


X → 0XA

0XA → 0YB

YBA → 1CYB

CY → Y0

1Y0 → 10


Aus dem Startsymbol X macht man gleich viele 0en (links) und As (rechts).

Nachdem der Marker X in Y umgewandelt wurde, produziert man die 1en mit einem Platzhalter für die rechten 0en. 

Am Ende macht man aus den Cs rechte 0en.

Der letzte Schritt lässt den Marker Y verschwinden.

A,B,C,X und Y sind die Nichtterminalsymbole, 0 und 1 die Terminalsymbole.

So ähnlich müsste es gehen.


Kommentar von Schachpapa ,

Sorry, war Quatsch ;-)

X => 0X1B
B1 => 1B
X1 => 1X
X => Y
YB => 0Y
Y$ => $

Nach Anwendung der ersten Regel habe ich z.B.
000X1B1B1B also 0^nX(1B)^n

darauf kann ich n-1 mal die zweite Regel anwenden und erhalte
000X111BBB also 0^nX1^nB^n

mit der dritten Regel schiebe ich den Marker X zwischen die 1er und die B-Gruppe:
000111XBBB also 0^n1^nXB^n

dann mache ich mit der vierten aus X Y und dann aus Bs 0en
000111000Y

Die letzte Regel soll prüfen, ob rechts neben dem Y das Ende erreicht ist, wenn ja soll das Y verschwinden. Wenn das so nicht geht, muss man mit XE beginnen und am Ende aus YE das leere Wort erzeugen.

Wenn du die Lösung hast, wäre es nett, sie hier zum Vergleich einzustellen ...

Kommentar von Schachpapa ,

Noch 'ne Korrektur:

So wie es jetzt ist, könnte man auf 0X1B die X1 => 1X Regel anwenden und erhält dann 01XB, danach X => 0X1B führt zu 010X1BB

weiter 0101XBB => 0101YBB => 01010YB => 010100Y => 010100

also muss jede Phase einen anderen Marker haben:

 

X => 0X1B

B1 => 1B

X => Y

Y1 => 1Y

Y => Z

ZB => 0Z

Z$ => $

Wenn du die Lösung hast, bittte unbedingt hier posten. Ich will das jetzt wissen ;-)

Keine passende Antwort gefunden?

Fragen Sie die Community