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=2749)
Geschrieben von Schnecke am 11.01.2016 um 21:51:
Kontextfreie Grammatik
Hallo Leute,
habe eine Sprache vorliegen, zu der ich die kontextfreie Grammatik finden möchte, jedoch komme ich nicht wirklich drauf, unabhängig davon, welche Regeln ich bislang aufgestellt habe. Die Sprache lautet:
L = {x^a y^b z^c | a < b oder b < c}
Über einen Denkanstoß wäre ich sehr dankbar.
Liebe Grüße
Geschrieben von Karlito am 12.01.2016 um 13:23:
Hallo Schnecke,
wir haben drei Fälle:
a<b, b<c und a<b<c.
Führen wir doch für die Bedingungen a<b und b<c Produktionsregeln ein, welche die Verhältnisse sicherstellen.
![[latex]<br />
A & \rightarrow & aAb~|~C<br />
C & \rightarrow & Cb~|~b<br />
B & \rightarrow & bBc~|~D<br />
D & \rightarrow & Dc~|~c<br />
[/latex]](http://www.matheboard.de/latex2png/latex2png.php?<br />
A & \rightarrow & aAb~|~C<br />
C & \rightarrow & Cb~|~b<br />
B & \rightarrow & bBc~|~D<br />
D & \rightarrow & Dc~|~c<br />
)
Und fassen alle Produktionen so zusammen, dass alle Möglichkeiten gegeben sind.
![[latex]<br />
S & \rightarrow & A~|~AD~|~B~|~FB<br />
F & \rightarrow & aF~|~a<br />
[/latex]](http://www.matheboard.de/latex2png/latex2png.php?<br />
S & \rightarrow & A~|~AD~|~B~|~FB<br />
F & \rightarrow & aF~|~a<br />
)
Ich hoffe, der Fehlerteufel hat sich nicht irgendwo eingeschlichen.
Gruß,
Karlito
Forensoftware: Burning Board, entwickelt von WoltLab GmbH