Informatiker Board (http://www.informatikerboard.de/board/index.php)
- Themengebiete (http://www.informatikerboard.de/board/board.php?boardid=1)
--- Theoretische Informatik (http://www.informatikerboard.de/board/board.php?boardid=5)
---- formale Sprachen (http://www.informatikerboard.de/board/board.php?boardid=12)
----- Kontextfreie Grammatik (http://www.informatikerboard.de/board/thread.php?threadid=2267)
Geschrieben von coooo am 10.05.2015 um 23:44:
Kontextfreie Grammatik
Hallo,
habe unten die Aufgabenstellung. Es geht darum, eine Grammatik für die Sprache:
wabawr zu entwerfen.
Wie gehe ich hier vor? Die Grammatik soll kontextfrei sein, jedoch steht "W" links und "Wr"rechts vom festen String "aba"
Geschrieben von Karlito am 11.05.2015 um 00:02:
Kontextfrei heißt doch nur, dass auf der linken Seite der Produktionen nur einzelne Nichtterminale stehen dürfen. Auf der rechten Seite kann so gut wie alles stehen.
geht also. Das ist dein Handwerkszeug.
Gruß,
Karlito
Geschrieben von coooo am 11.05.2015 um 21:24:
Danke.
Als nächstes habe ich: S---> aba
Geschrieben von Karlito am 11.05.2015 um 23:15:
Das ist gut. Damit hast Du den Abschluss. Nun Fehlen die Produktionen, die
und
erzeugen. Folgende Grammatik (nur Produktionen angegeben) erzeugt die Sprache
:
Gibt dir das den entscheidenden Hinweis?
Gruß,
Karlito
Geschrieben von coooo am 11.05.2015 um 23:43:
Hm, ich weiß nicht so recht.
Würde die Aufgabe so lösen:
S ---> xSy
S ---> aba
S---> aSb
x---> AB
y ---> BA
A--- > a | e
B ---> b | e
Geschrieben von Karlito am 11.05.2015 um 23:51:
Viel einfacher!
Verstehst Du es?
Gruß,
Karlito
Geschrieben von coooo am 12.05.2015 um 00:01:
Verstehe ich es richtig, dass ich S---> aba nur zum Schluss benutzen kann? da dort kein S enthalten ist?
Geschrieben von Karlito am 12.05.2015 um 00:14:
Ja, somit wird die "Reihe" der Produktionen terminiert, da es kein weiteres Nichtterminal gibt,.
Forensoftware: Burning Board, entwickelt von WoltLab GmbH