Как мы знаем, для регулярной грамматики у нас есть алгоритм для получения ее регулярного выражения.
Но если данная грамматика является контекстно-свободной грамматикой (но она генерирует только обычный язык), например
Существует ли какой-либо существующий алгоритм, который может получить регулярное выражение в целом?
Спасибо!
В самом общем смысле решения нет. Проблема определения регулярности CFG неразрешима (теорема Грейбаха, последние 3 страницы http://www.cis.upenn.edu/~jean/gbooks/PCPh04.pdf ) Если бы мы могли преобразовать CFG в регулярные выражения, мы могли бы использовать этот алгоритм для любой грамматики и использовать его успех/неудачу для определить, является ли язык правильным.
Вместо этого, когда известно, что CFG производит обычный язык, либо его язык уже известен (и, следовательно, может быть напрямую преобразован в RegEx), либо есть какое-то свойство грамматики, которое нужно использовать. Каждое свойство имеет собственный алгоритм преобразования в RegEx.
Например, если грамматика линейна вправо, каждая продукция имеет форму A->bC или А->а. Это может быть преобразовано в NFA, где:
1) Существует состояние для каждого нетерминала плюс состояние принятия.
2) Начальный символ S является начальным состоянием.
3) A->bC — переход от A к B на входе b
4) A->a — переход из A в состояние accept на входе a.
Затем этот NFA можно преобразовать в регулярное выражение путем исключения состояния (страницы 5-8 http://www.math.uaa.alaska.edu/~afkjm/cs351/handouts/regular-expressions.pdf). ). Аналогичный процесс для леволинейных грамматик поменялся бы состояниями start и accept.
Кроме того, можно использовать свойства замыкания обычных языков. Например, язык в вопросе нелинейный, но его можно записать как S->S'b, S'->aA. Теперь S' линейно справа, а S является конкатенацией двух непересекающихся линейных грамматик. Объедините два выражения для окончательного выражения. Аналогичная логика для союза.
