Пускай автоматы в Контекст бесплатно: как это сделать?

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 

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

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

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

Answer 1

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

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