Обычная грамматика для моего регулярного выражения/DFA

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

X -> aY
X -> a,

в котором X — произвольный нетерминал, a — произвольный терминал. Правило 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

ef*g? Здесь у нас есть буква 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)*