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

... komplette Frage anzeigen

2 Antworten

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.


Antwort bewerten Vielen Dank für Deine Bewertung
Kommentar von Schachpapa
17.08.2016, 17:10

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 ...

0

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 :)

Antwort bewerten Vielen Dank für Deine Bewertung
Kommentar von titan777
17.08.2016, 07:15

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 :)

0

Was möchtest Du wissen?