Regular Grammar моему Regex/DFA

Question

я следующее регулярное выражение: ((ABC) + г) | (? Эф * г)

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

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

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

S → аТ

T → б

T → C

T → Ds

S → еТ

S → eS

T → ε

T → F

Т → Fs

T → Gs

С наилучшими пожеланиями Patrick

Answer 1

типом 3 Хомским являются классом регулярных грамматик суженных к использованию следующих правил:

X -> aY 
X -> a, 

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

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

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

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

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

ef * 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 *) Ьс (а | б | в) *