Pushdown автоматы до контекста бесплатно: как это сделать?

Question

Мне нужно написать CFG, который генерирует следующие автоматы.

Я знаю, что такой переход:

-es, es; S lead to a rule like S-> es
-es, B; es lead to a rule like B -> es
-es, B; aB lead to a rule like B-> aB

es обозначает пустую строку.

Но я не знаю, как обращаться с такими правилами, как "c, a; a". Кто-нибудь может мне помочь? Спасибо.

http://tonguim.free.fr/divers/automata.jpg

Answer 1

Вообще говоря, каждое производство - это конечный автомат, который показывает прогресс синтаксического анализатора в этом производстве.

Стек, используемый автоматом, является стеком таких состояний производства.Каждый раз, когда вы спускаетесь в производство, вы нажимаете на его начальное состояние.Каждый раз, когда вы заключаете один, вы выводите его окончательное состояние.Терминалы можно рассматривать как вырожденные производства, конечные автоматы которых имеют одно состояние.