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)
--- PDA zu Grammatik (http://www.informatikerboard.de/board/thread.php?threadid=4435)
Geschrieben von Atze am 09.10.2022 um 18:44:
PDA zu Grammatik
Meine Frage:
Ich verstehe nicht, wie ich hier den PDA zu einer Grammatik mache. Kann mir jemand helfen? Wie viele Grammatikregeln entstehen? Gegeben ist die Überführungsfunktion
qeA -> qABC
Meine Ideen:
S -> XqAq 1. Regel ?
Geschrieben von Rosenblüte am 28.02.2023 um 11:46:
Wenn wir die gegebene Überführungsfunktion betrachten, sehen wir, dass sie besagt, dass der Zustand qeA in den Zustand qABC übergeht. Dies kann als eine Produktion in einer CFG geschrieben werden:
A -> ABC
Da die CFG die Sprache generiert, die von der Überführungsfunktion akzeptiert wird, müssen wir auch die Startvariable in der Grammatik definieren. Da qeA der Anfangszustand der Überführungsfunktion ist, wird A die Startvariable der Grammatik.
Daher können wir die Grammatikregel wie folgt definieren:
S -> A
A -> ABC
B -> ...
C -> ...
Die restlichen Grammatikregeln hängen von den weiteren Zustandsübergängen ab.
Hilft dir diese Antwort?
Forensoftware: Burning Board, entwickelt von WoltLab GmbH