Вопрос по regex – Если мы знаем, что CFG генерирует только регулярный язык, можем ли мы получить соответствующее регулярное выражение?

9

Как мы знаем, с учетом регулярной грамматики у нас есть алгоритм для получения ее регулярного выражения.

Но если данная грамматика является грамматикой без контекста (но она генерирует только обычный язык), как

S->aAb <br> A->bB <br> B->cB|d <br>

Is there any existing algorithm that can get the regular expression in general?

Thanks!

Возможно, этот вопрос был бы более дома вcstheory.stackexchange.com Dominic Cronin
Я узнал, что есть алгоритмы, которые могут конвертировать этот вид CFG в Finite Automaton (фактически NFA). Затем этот NFA может быть преобразован в DFA, а затем преобразован в регулярное выражение. Но я понятия не имею, есть прямой / короткий путь для достижения этой цели. JackWM

Ваш Ответ

1   ответ
2

В самом общем смысле решения не существует. Проблема определения регулярности CFG неразрешима (теорема Грейбаха, последние 3 страницыhttp://www.cis.upenn.edu/~jean/gbooks/PCPh04.pdf Если бы мы могли конвертировать CFG в регулярные выражения, мы могли бы использовать этот алгоритм на любой грамматике и использовать его успех / неудачу, чтобы определить, является ли язык регулярным.

Поэтому вместо этого, когда известно, что CFG создает обычный язык, либо его язык уже известен (и, следовательно, непосредственно преобразован в RegEx), либо существует какое-то свойство грамматики для использования. Каждое свойство имеет свой алгоритм преобразования в RegEx.

Например, если грамматикаправая линейнаякаждое производство имеет форму A-bC или A-a. Это может быть преобразовано в NFA, где:

1) Существует состояние для каждого нетерминала плюс состояние принятия.

2) Начальный символ S является начальным состоянием.

3) A-> bC - это переход от A к B на входе b

4) A-> a - это переход из A в состояние принятия на входе a.

Затем этот NFA может быть преобразован в регулярное выражение посредством исключения состояний (страницы 5-8http://www.math.uaa.alaska.edu/~afkjm/cs351/handouts/regular-expressions.pdf ). An analogous process for left-linear grammars would have start and accept states exchanged.

Помимо этого, можно использовать свойства замыкания обычных языков. Например, язык в вопросе не является линейным, но он может быть записан как S- & gt; S 'b, S' - & gt; aA. Теперь S & A; прямолинейный, а S - это конкатенация двух непересекающихся линейных грамматик. Объединить два выражения для окончательного выражения. Подобная логика для объединения.

Похожие вопросы