Преобразования регулярных выражений в регулярную грамматике/правая линейную грамматику

Question

Я хотел бы, чтобы убедиться, что я преобразование этого регулярного выражения в правых линейные грамматик правильно на основе информации из этого предыдущего вопроса и замечательного ответа по Grijesh: Left-Linear and Right-Linear Grammars

Здесь возникает вопрос: «Напишите правильную (правую линейную) грамматику, которая порождает множество строк, обозначенных регулярным выражением ((10) + (011 + 1) +) * (0 + 101) *."

А вот грамматик я застроенные, с моим последним из которых на дне:

1: 
S --> 1 

0: 
S --> 0 

10: 
S --> 1A 
A --> 0 

(10)+: 
S --> 1A 
A --> 0 | 0S 

011: 
S --> 0A 
A --> 1B 
B --> 1 

(011 + 1): 
S --> 0A | 1 
A --> 1B 
B --> 1 

(011 + 1)+: 
S --> 0A | 1 | 1S 
A --> 1B 
B --> 1 | 1S 

(10)+ (011 + 1)+: 
S --> 1A 
A --> 0S | 0B 
B --> 0C | 1 | 1B 
C --> 1D 
D --> 1 | 1B 

((10)+ (011 + 1)+)*: 
S --> 1A | ε 
A --> 0S | 0B 
B --> 0C | 1 | 1B 
C --> 1D 
D --> 1 | 1B 

0: 
S --> 0 

101: 
S --> 1A 
A --> 0B 
B --> 1 

(0 + 101): 
S --> 0 | 1A 
A --> 0B 
B --> 1 

(0 + 101)*: 
S --> 0 | 1A | ε 
A --> 0B 
B --> 1 

((10)+ (011 + 1)+)* (0 + 101)*: 
S --> 1A | ε | E 
A --> 0S | 0B 
B --> 0C | 1 | 1B 
C --> 1D 
D --> 1 | 1B | 1E 
E --> 0 | 1F | ε 
F --> 0G | 0E 
G --> 1 | 1E 

Может кто-нибудь помочь мне проверить, является ли правильным? Спасибо, пучки! : D

Answer 1

Все выглядит вплоть до здесь:

((10)+ (011 + 1)+)*: 
S --> 1A | ε 
A --> 0S | 0B 
B --> 0C | 1 | 1B 
C --> 1D 
D --> 1 | 1B 

Ваша грамматика для внутреннего выражения является правильным:

(10)+ (011 + 1)+: 
S --> 1A 
A --> 0S | 0B 
B --> 0C | 1 | 1B 
C --> 1D 
D --> 1 | 1B 

Обратите внимание, что единственным отличием является вы позволили пустая строка будет производиться , Закрытие Kleene добавляет больше, чем просто пустую строку: она позволяет повторять весь шаблон. Возможно, это можно было бы исправить добавлением производств B --> 1S и D --> 1S к первой грамматике, что позволило бы произвольно повторить.

То же самое происходит ошибка в этой паре:

(0 + 101): 
S --> 0 | 1A 
A --> 0B 
B --> 1 

(0 + 101)*: 
S --> 0 | 1A | ε 
A --> 0B 
B --> 1 

Вторая грамматика следует добавить постановки S --> 0S и B --> 1S, чтобы для произвольного количества повторений.

Остальная часть конструкции выглядит правильно и вместе с исправлениями, упомянутыми выше, должна содержать правильную грамматику.

Примечание: Вы можете сделать это алгоритмически путем:

1. Использование алгоритма для получения НКА из регулярного выражения
2. Использование алгоритма для получения ДКА из НКА
3. (Необязательно) Использование алгоритм, чтобы свести к минимуму DFA
4. с использованием алгоритма для получения регулярной грамматики из DFA

T он длинный полюс в вычислительной палатке - это шаг 2; этот шаг даже не нужен, если вы можете вместо полного определения автомата устранить эпсилон/лямбда-переходы. Причина, по которой это было бы достаточно, состоит в том, что процесс превращения DFA в регулярную грамматику превращает состояния в нетерминальные символы и отображает переход f(q, s) = q' в производство q := sq' с q := s также, если принимает q'. Пока у NFA нет пустых переходов, вы можете продолжить и использовать это.