Informatiker Board | Druckvorschau: Grammatik für die Sprache a^2n b^n c^2n

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)
----- Grammatik für die Sprache a^2n b^n c^2n (http://www.informatikerboard.de/board/thread.php?threadid=3860)

Geschrieben von Info_:) am 13.02.2018 um 19:30:

Grammatik für die Sprache a^2n b^n c^2n

Hallo,

ich möchte zur Sprache L {a^2n b^n c^2n} mit n Element der Natürlichen Zahlen. Eine Grammatik aufstellen. Leider habe ich bis jetzt keine vernünftige Grammatik für die Sprache gefunden, weshalb ich hier nach Hilfe suche.

Wörter der Sprache wären bsp: aabcc, aaaabbcccc, ich komme jedoch nicht auf die Grammatik.

Für Hilfen wäre ich sehr dankbar!

Geschrieben von NixJava am 13.02.2018 um 22:31:

Moin,

mein Vorschlag für die Sprache $[latex]L = \{a^{2n}b^nc^{2n} \ | \ n \ge 0\}[/latex]$ :

$[latex]\{S \to aa\hat{S}Bcc | \varepsilon, \ \hat{S} \to aa\hat{S}Bcc, \ cB \to Bc, \ \hat{S}B \to b, \ bB \to bb\}[/latex]$

Die Idee dahinter:
* Die erste Regel macht auch $[latex]\varepsilon[/latex]$ möglich.
* Mit der zweiten Ableitungsregel kann man das Wort auf die entsprechende Länge [latex]n[/latex]

bringen.
* Mit der dritten Regel werden die B in die Mitte geschoben.
* Die vierte Regel erstellt das erste b (wenn die gewünschte Länge erreicht wurde)
* Die letzte Ableitungsregel wandelt die B in b um.

Ich habe auf kontextfreie Umwandlungen wie $[latex]B \to b[/latex]$ verzichtet, damit die B nicht zu früh abgeleitet werden können und es Probleme gibt.

Die Grammatik ist vom Typ 0 und ohne Gewähr auf Richtigkeit.