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.
![[latex]<br />
S \rightarrow xSy [/latex]](http://www.matheboard.de/latex2png/latex2png.php?<br />
S \rightarrow xSy )
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
![[latex]w[/latex]](http://www.matheboard.de/latex2png/latex2png.php?w)
und
![[latex]w^r[/latex]](http://www.matheboard.de/latex2png/latex2png.php?w^r)
erzeugen. Folgende Grammatik (nur Produktionen angegeben) erzeugt die Sprache
![[latex]\mathcal{L} = \{a^nb^n~|~n\in \mathbb{N}\}[/latex]](http://www.matheboard.de/latex2png/latex2png.php?\mathcal{L} = \{a^nb^n~|~n\in \mathbb{N}\})
:
![[latex]<br />
S & \rightarrow & \varepsilon<br />
S & \rightarrow & aSb<br />
[/latex]](http://www.matheboard.de/latex2png/latex2png.php?<br />
S & \rightarrow & \varepsilon<br />
S & \rightarrow & aSb<br />
)
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!
![[latex]<br />
S & \rightarrow & aba<br />
S & \rightarrow & aSa<br />
S & \rightarrow & bSb<br />
[/latex]](http://www.matheboard.de/latex2png/latex2png.php?<br />
S & \rightarrow & aba<br />
S & \rightarrow & aSa<br />
S & \rightarrow & bSb<br />
)
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