 Grammatik für die Sprache a^2n b^n c^2n |
Info_:)
unregistriert
 |
|
| 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!
|
|
13.02.2018 19:30 |
|
|
NixJava
unregistriert
|
|
Moin,
mein Vorschlag für die Sprache ![[latex]L = \{a^{2n}b^nc^{2n} \ | \ n \ge 0\}[/latex]](http://www.matheboard.de/latex2png/latex2png.php?L = \{a^{2n}b^nc^{2n} \ | \ n \ge 0\}) :
![[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]](http://www.matheboard.de/latex2png/latex2png.php?\{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\})
Die Idee dahinter:
* Die erste Regel macht auch ![[latex]\varepsilon[/latex]](http://www.matheboard.de/latex2png/latex2png.php?\varepsilon) möglich.
* Mit der zweiten Ableitungsregel kann man das Wort auf die entsprechende Länge ![[latex]n[/latex]](http://www.matheboard.de/latex2png/latex2png.php?n) 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]](http://www.matheboard.de/latex2png/latex2png.php?B \to b) 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.
|
|
|
13.02.2018 22:31 |
|
|
|
