Можно ли использовать регулярные выражения для распознавания любого языка без контекста?

Question

Я знаю, что пакеты регулярных выражений могут распознавать более широкий набор языков, чем обычные языки, но использование рекурсивного регулярного выражения в регулярное выражение Python для поиска арифметических выражений в текстовых строках заставляет задуматься, возможно лираспознает любой контекстно-свободный язык с помощью регулярных выражений, и если нет, то может ли кто-нибудь привести встречный пример?

Answer 1

В основном этот ответ взят из этого отличного сообщения в блоге.

Таким образом, краткий ответ таков: регулярные выражения с рекурсивным расширением могут распознавать любую контекстно-свободную грамматику.

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

(?<name> ...) определяет шаблон регулярного выражения, который впоследствии может быть повторно использован с (?&name).

Любую контекстно-свободную грамматику можно записать в виде набора правил следующих форм:

• A -> BC
• A -> a

Если мы можем написать эти правила как регулярное выражение, регулярное выражение может распознавать любой контекстно-свободный язык. Единственное интересное правило здесь первое.

Во-первых, если правило является рекурсивным слева, нам нужно переписать его в праворекурсивное правило, поскольку регулярное выражение поддерживает только правую рекурсию. Такое переписывание всегда возможно. Теперь мы можем написать все такие правила следующим образом:

A -> BC
A -> DE
(?<A>(?&B)(?&C)|(?&D)(?&E))

Это позволяет определять произвольные правила CFG, поэтому нам нужно только определить их все, а затем сопоставить с исходным правилом.

(?(DEFINE)define rules here)^(?&initial)$

Здесь (?(DEFINE)...) объявляет правила без соответствия, а initial относится к начальному правилу грамматики.

Прошло некоторое время с тех пор, как я слышал теоретические курсы CS, поэтому, пожалуйста, поправьте меня, еслиесть ошибки:)