Konvertieren Sie CFG in PDA

Gibt es Regeln oder Methoden, um eine kontextfreie Grammatik in Push-Down-Automaten umzuwandeln?

Ich habe bereits einige Folien online gefunden , konnte sie aber nicht verstehen.

In Folie 10 spricht er über einige Regeln. Kann jemand das erklären?

context-free formal-grammars pushdown-automata simulation Makakas
quelle

Überprüfen Sie Wikipedia und diese Frage . Die Idee ist, das Wort (unter Verwendung der Grammatik) auf dem Stapel zu generieren und es mit der Eingabe abzugleichen. Der Trick besteht darin, es parallel zu machen - einen Teil des Wortes zu generieren, es zu überprüfen, etwas mehr zu generieren, es zu überprüfen usw.

Ran G.

Ein Video, das dieses Thema behandelt und leicht zu verstehen ist: youtube.com/watch?v=MJ9xNavURY8

Ran G.

Antworten:

Die tatsächlichen Regeln für diese Konstruktion sind auf Folie 7 in dieser Präsentation angegeben. Wikipedia nennt diese Regeln "übereinstimmen" und "erweitern".

Die Folien, die Sie verwenden, stammen anscheinend aus einem Kurs von Jeff Ullman. (Einer der Autoren eines berühmten Buches über formale Sprachen und Automaten). Er hat auch einen Online-Kurs zu diesem Thema vorbereitet , in dem er die Details wohl selbst erklären wird.

Hendrik Jan.
quelle