Как преобразовать обычную грамматику в конечный автомат? - PullRequest
Новая
       81

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

0 голосов
/ 11 февраля 2020

Как можно преобразовать правильную грамматику в конечный автомат (ФА)? Например, как будет выглядеть конечный автомат, соответствующий следующей регулярной грамматике? 

VN = {S, B, D} (nonterminals)
VT = {a, b, c} (terminals)
 P = {S -> aB, S -> bB, B -> bD, D -> b, D -> aD, B -> cB, B -> aS} (productions)

1 Ответ

1 голос
/ 11 февраля 2020

Хорошая новость в том, что это не так уж сложно. Идея состоит в том, что каждый из нетерминалов станет состоянием в недетерминированном c конечном автомате, принимающем язык грамматики, и произведения станут переходами. Наш NFA будет иметь состояния S, B и D и будет переходить между этими состояниями в соответствии с правилами производства. Наш NFA выглядит так: 

       ___a__      _a_
      /      \    /   \
      |      |    \   /
      V      |     \ /
----->S-a,b->B--b-->D
            / \
           /   \
           \_c_/

Было одно свисающее производство D -> b, которое мы еще не добавили. Нам нужно ввести другое состояние, не соответствующее нетерминальному символу, чтобы позволить нам перейти от D на b и принять несколько строк: 

       ___a__      _a_
      /      \    /   \
      |      |    \   /
      V      |     \ /
----->S-a,b->B--b-->D--b-->Q
            / \
           /   \
           \_c_/

Теперь, если мы сделаем S начальным состоянием, а Q - принимающим состоянием У нас есть NFA, который работает. Если мы хотим DFA, мы могли бы заметить, что этот FA только недетерминирован c, потому что нам не хватает необходимых переходов из состояний S, D и Q. Мы можем добавить отсутствующие переходы, введя новое мертвое состояние X, которое будет отслеживать NFA, который мы только что получили, потерпел крах в некоторый момент во время его обработки: 

       ___a__      _a_
      /      \    /   \
      |      |    \   /
      V      |     \ /
----->S-a,b->B--b-->D--b-->Q
      |     / \     |      |
      |    /   \    |      |    a,b,c
      c    \_c_/    c    a,b,c  /   \
      |             |      |    \   /
      V             V      V     \ /
      +-------------+------+----->X
...