Konwertuj CFG na PDA

Czy istnieje zestaw reguł lub metod służących do konwersji gramatyki bezkontekstowej na automaty wypychające?

Znalazłem już kilka slajdów w Internecie, ale nie byłem w stanie ich zrozumieć.

W slajdzie 10 mówi o niektórych zasadach, czy ktokolwiek mógłby to wyjaśnić?

— makakas
źródło

sprawdź wikipedię i to pytanie . Chodzi o to, aby wygenerować słowo (używając gramatyki) na stosie i dopasować je do danych wejściowych. Sztuką jest robienie tego równolegle - generowanie części słowa, sprawdzanie go, generowanie trochę więcej, sprawdzanie itp.

— Ran G.

Film, który obejmuje ten temat i jest łatwy do zrozumienia: youtube.com/watch?v=MJ9xNavURY8

— Ran G.

Rzeczywiste zasady tej konstrukcji podano na slajdzie 7 w tej prezentacji. Wikipedia nazywa te reguły „dopasowaniem” i „rozwinięciem”.

Wydaje się, że slajdy, których używasz, pochodzą z kursu Jeffa Ullmana. (Jeden z autorów słynnej książki o językach formalnych i automatach). Przygotował także internetowy kurs na ten temat, na którym chyba sam wyjaśni szczegóły.

— Hendrik Jan
źródło