Преобразуйте регулярное выражение в CFG
Как я могу преобразовать некоторый регулярный язык в его эквивалентную Контекстно-свободную грамматику? Действительно ли это необходимо создать соответствие DFA тому регулярному выражению или является там некоторым правилом для такого преобразования?
Например, рассмотрите следующее регулярное выражение
01+10 (11) *
Как я могу описать грамматику, соответствующую вышеупомянутому РЕ?
2 ответа
Заменить A + B на грамматику
G -> A G -> BЗаменить A * на
G -> (пусто) G -> AGИзмените AB на
G -> AB
и продолжайте рекурсивно A и B. Базовые случаи - пустой язык (без продукции) и один символ.
В вашем случае
A -> 01
A -> 10B
B -> (empty)
B -> 11B
Если язык описывается конечным автоматом:
- использовать состояния как нетерминальные символы
- использовать язык как набор оконечных символов
- добавить переход p -> aq для любого перехода p -> q на букве a в исходном автомате
- использовать начальное состояние в качестве начального символа в грамматике
Думаю, вы имеете в виду преобразовать его в формальную грамматику с правилами вида V-> w, где V - нетерминал, а w - строка терминалов / нетерминалы. Для начала вы можете просто сказать (смешивая синтаксис CFG и регулярного выражения):
S -> 01+10(11)*
Где S - начальный символ. Теперь давайте разберем его немного (и добавим пробелы для ясности):
S -> 0 A 1 0 B
A -> 1+
B -> (11)*
Ключ состоит в том, чтобы преобразовать * es и + es в рекурсию. Сначала мы преобразуем звезду Клини в плюс, вставив промежуточное правило, которое принимает пустую строку:
S -> 0 A 1 0 B
A -> 1+
B -> (empty)
B -> C
C -> (11)+
Наконец, мы преобразуем нотацию + в рекурсию:
S -> 0 A 1 0 B
A -> 1
A -> A 1
B -> (empty)
B -> C
C -> 11
C -> C 11
Для обработки ] x? , просто разделите его на правило, производящее пустое, и правило, производящее x.