Как преобразовать линейную грамматику в конечный автомат

Мне нужно преобразовать линейную правую грамматику в конечный автомат. Грамматика

S —> bA|aD|bC
А —> aC|bA
C —> bB|aA|b
B —> aD|bC|a
D —> aA|aC

Обычно задача решается следующим образом: Каждому состоянию сопоставляем нетерминал. Если есть переход из X в Y по состоянию и, добавляем правило X → aY. Чтобы добавить правило конечного состояния X → ε. Для ε-переходов - X → Y.

Например:

A → aB | cC
B → bD | cE
C → ε
D → aB | cC
E → aB | cC

Решение

Вопросы.

  1. Как быть, если есть связь А и А, например, А -> аС | ба.
  2. Как работать со структурами C -> bB | аА | b, конец только b.

state-machine compiler-construction discrete-mathematics
person tbutton    schedule 06.06.2013    source источник

Ответы (1)


arrow_upward
2
arrow_downward

1] Вы можете создавать циклы (например, узел Z может добавить букву o, а затем перейти к узлу Z)

2] Используйте состояние ловушки. Вы не можете никуда двигаться оттуда, но все равно требуется ход (и, следовательно, буква), чтобы добраться туда.

person Daniel    schedule 06.06.2013
comment
Благодарю вас! Я постараюсь это сделать. - person tbutton; 06.06.2013
comment
@tbutton нет проблем. Если это поможет вам, не стесняйтесь отметить ответ как полезный;) - person Daniel; 06.06.2013