Convertir CFG en PDA

9

Existe-t-il un ensemble de règles ou de méthodes pour convertir une grammaire sans contexte en automates push down?

J'ai déjà trouvé des diapositives en ligne mais je n'ai pas pu les comprendre.

Dans la diapositive 10, il parle de certaines règles. Quelqu'un pourrait-il expliquer cela?

context-free formal-grammars pushdown-automata simulation makakas
la source
2
vérifier wikipedia, et cette question . L'idée est de générer le mot (en utilisant la grammaire) sur la pile et de le faire correspondre à l'entrée. L'astuce est de le faire en parallèle - générer une partie du mot, le vérifier, en générer plus, le vérifier, etc.
Ran G.
2
Une vidéo qui couvre ce sujet et est facile à comprendre: youtube.com/watch?v=MJ9xNavURY8
Ran G.

Réponses:

1

Les règles réelles de cette construction sont données sur la diapositive 7 de cette présentation. Wikipedia appelle ces règles "correspondre" et "étendre".

Il semble que les diapositives que vous utilisez proviennent d'un cours de Jeff Ullman. (Un des auteurs d'un célèbre livre sur les langages formels et les automates). Il a également préparé un cours en ligne sur le sujet, où je suppose qu'il expliquera lui-même les détails.

Hendrik Jan
la source