Ваша грамматика:
S -> aA | bB
A -> aC | bC | a | b
B -> aC | bC | a | b
C -> aA
Бывает, что грамматика правильная-правильная.Как таковой, он описывает обычный язык и может быть легко преобразован в детерминированный конечный автомат:
q s q'
S a A
S b B
A a (C)
A b (C)
B a (C)
B b (C)
(C) a A
(C) b [D]
[D] a [D]
[D] b [D]
Здесь S - начальное состояние, C - принимает, а D - мертв.Чтобы получить регулярное выражение, обработайте этот автомат как NFA и начните заменять метки символов регулярными выражениями, исключая состояния:
S = aA + bB
A = aC + bC + a + b
B = aC + bC + a + b
C = aA + bD
D = aD + bD
Обратите внимание, что D = aD + bD = (a + b)D имеет значение true, только если D = {}.Перезапись:
S = aA + bB
A = aC + bC + a + b
B = aC + bC + a + b
C = aA
Теперь мы можем безопасно исключить C путем подстановки:
S = aA + bB
A = aaA + baA + a + b = (aa + ba)A + (a + b)
B = aaA + baA + a + b = (aa + ba)A + (a + b)
Теперь мы можем использовать правило Z = xZ + y => Z = x*y:
S = aA + bB
A = (aa + ba)*(a + b)
B = aaA + baA + a + b = (aa + ba)A + (a + b)
Теперь замените:
S = aA + bB
A = (aa + ba)*(a + b)
B = (aa + ba)(aa + ba)*(a + b) + (a + b)
Теперь еще раз:
S = a(aa + ba)*(a + b) + b((aa + ba)(aa + ba)*(a + b) + (a + b))
Теперь мы можем группировать подобные термины:
S = (a(aa + bb)* + b(aa + ba)(aa + ba)* + b)(a + b)
Обратите внимание, что b(aa + ba)(aa + ba)* + b может быть учтено b((aa + ba)(aa + ba)* + e) и что (aa + ba)(aa + ba)* + e = (aa + ba)*:
S = (a(aa + bb)* + b(aa + ba)*)(a + b)
Мы можем снова учесть:
S = (a + b)(aa + ba)*(a + b)
Это последнее выражение является хорошим, кратким, правильным регулярным выражением для вашего языка.По сути, это кодирует идею «увидеть один символ, затем увидеть другой символ, но если вы видите третий символ, лучше не быть ab».