Konwertuj CFG na PDA

9

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
2
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.
2
Film, który obejmuje ten temat i jest łatwy do zrozumienia: youtube.com/watch?v=MJ9xNavURY8
Ran G.

Odpowiedzi:

1

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