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)
--- kontextfreie Grammatik (http://www.informatikerboard.de/board/thread.php?threadid=2955)
Geschrieben von gmxfor am 17.04.2016 um 16:53:
kontextfreie Grammatik
Meine Frage:
Geben Sie eine kontextfreie Grammatik an, die genau die Sprache erzeugt, die durch den regulären Ausdruck
a(b|cc)*(a|e)
dargestellt wird.
Wie muss ich vorangehen?
Meine Ideen:
...
Geschrieben von eulerscheZahl am 17.04.2016 um 20:26:
Du hast 3 Bestandteile: a, (b|cc)* und a|e.
Generieren wir die doch direkt:
S -> aAB
Der erste Teil ist damit schon angedeckt.
B -> a|e ist auch einfach.
Was wird jetzt aus A?
Geschrieben von gmxfor am 18.04.2016 um 16:11:
A -> (b|cc)*
Geschrieben von eulerscheZahl am 18.04.2016 um 16:50:
Den Stern gibt es aber in einer Grammatik nicht.
Wie könnte man den umschreiben?
Geschrieben von gmxfor am 18.04.2016 um 17:06:
ich weiß nicht genau aber vielleicht:
{0,}
Geschrieben von eulerscheZahl am 18.04.2016 um 17:09:
Nein.
Du erzeugst einfach ein neues A, dann kannst du die Regel erneut anwenden:
A -> Ab | Acc
Eine Sache fehlt noch. Welche?
Geschrieben von gmxfor am 18.04.2016 um 17:14:
leider weiß ich es nicht
A-> bA | ccA das ist ja in dem Fall das gleiche
Geschrieben von eulerscheZahl am 18.04.2016 um 17:14:
Aber mit den Regeln allein geht das A nie weg. Also...?
Geschrieben von gmxfor am 18.04.2016 um 17:18:
ja b und cc sind ja in einer unendlichen Schleife wegen dem Stern, also kann man A nicht ersetzen
Geschrieben von eulerscheZahl am 18.04.2016 um 17:19:
Und was muss man tun, damit man das A trotzdem wegbekommt?
Geschrieben von gmxfor am 18.04.2016 um 17:24:
das A mit a generieren
Geschrieben von eulerscheZahl am 18.04.2016 um 17:27:
An die Möglichkeit hatte ich gar nicht gedacht, das ist aber auch möglich.
Ich hätte einen Epsilon Übergang verwendet.
Geschrieben von gmxfor am 18.04.2016 um 17:31:
dann würde es heißen
A -> Ab|Acc
A -> a
A -> ab|acc
oder
A -> Ab|Acc
A -> epsilon
A -> b|cc
Geschrieben von eulerscheZahl am 18.04.2016 um 17:34:
S -> Aa | Ae
A -> a | Ab | Acc
Geschrieben von gmxfor am 18.04.2016 um 17:36:
achso ok vielen Dank
Forensoftware: Burning Board, entwickelt von WoltLab GmbH