Регулярная грамматика для моего Regex/DFA

Question

У меня есть следующее регулярное выражение: ((abc)+d)|(ef*g?)

Я создал DFA (надеюсь, это правильно), который вы можете увидеть здесь

http://www.informatikerboard.de/board/attachment.php?attachmentid=495&sid=f4a1d32722d755bdacf04614424330d2

Задача состоит в том, чтобы создать правильную грамматику (иерархия Хомского типа 3), а я ее не понимаю. Но я создал обычную грамматику, которая выглядит так:

S → aT

T → b

T → c

T → dS

S → eT

S → eS

T → ε

T → f

T → fS

T → gS

С наилучшими пожеланиями, Патрик

Answer 1

Тип 3 Хомского - это класс регулярных грамматик, ограниченный использованием следующих правил:

X -> aY
X -> a,

в которой X является произвольным нетерминалом и произвольным терминалом. Правило A -> eps разрешено только если A нет ни в одной из правых сторон.

строительство

Мы замечаем, что регулярное выражение состоит из двух возможностей: (abc) + d или ef*g?, поэтому наши первые правила будут S -> aT а также S -> eP, Эти правила позволяют нам начать создавать одну из двух возможностей. Обратите внимание, что нетерминалы обязательно разные, это абсолютно разные непересекающиеся пути в соответствующем автомате. Далее мы продолжим с обоими регулярными выражениями отдельно:

(abc) + У нас есть по крайней мере одна последовательность abc, за которой следует 0 или более вхождений, нетрудно увидеть, что мы можем смоделировать это следующим образом:

S -> aT
T -> bU
U -> cV
V -> aT   # repeat pattern
V -> d    # finish word

эф * г? Здесь у нас есть e, за которым следует ноль или более f символов и необязательный g, поскольку у нас уже есть первый символ (одно из первых двух правил дало нам это), мы продолжаем так:

S -> eP
S -> e    # from the starting state we can simply add an 'e' and be done with it,
          # this is an accepted word!
P -> fP   # keep adding f chars to the word
P -> f    # add f and stop, if optional g doesn't occur
P -> g    # stop and add a 'g'

Заключение

Соедините их вместе, и они сформируют грамматику для языка. Я пытался записать ход мыслей, чтобы вы могли понять это.

В качестве упражнения попробуйте следующее регулярное выражение: (a+b*)? Bc(a|b|c)*