Может ли POSIX BRE выразить все обычные языки?

13

Похоже, что «Основные регулярные выражения», как определено в POSIX.1-2008 , не поддерживают чередование a|b(хотя некоторые реализации grep распознают экранированную версию \|).

Поскольку регулярные языки по определению замкнуты относительно объединения, означает ли это, что POSIX BRE обладает меньшей выразительной силой, чем конечный автомат? Или есть какой-то способ имитации чередования с использованием других конструкций?

Стив Кобес
источник

Ответы:

17

Действительно, язык POSIX BRE не может выражать все регулярные выражения, потому что в нем нет чередования. Он даже не может распознать все конечные языки, не говоря уже о всех обычных языках.

Например, не распознается как BRE. Чтобы доказать это, рассмотрим, какой может быть синтаксическая форма верхнего уровня:{ab,ba}

  • Это не может быть одна из односимвольных форм, поскольку в языке есть слова длиной .>1
  • R
  • R{m,n}m=n=1
  • R1R2ab
    • R1abR2R1{ab,ba}
    • R1aabR2bR1R2ubR1uR1aba
    • R1abaRabR1R2

Когда «мы возвращаемся к исходной проблеме», это означает, что единственное решение, чтобы найти BRE, распознающий язык, - это найти меньший BRE, имеющий то же свойство. Это бесконечный спуск , поэтому нет BRE, который обладает желаемым свойством.

Я не думаю, что есть «хорошая» характеристика BRE-распознаваемых языков, например, языков, распознаваемых «хорошим» классом автоматов.

{www{a,b}}\(.*\)\1

Жиль "ТАК - прекрати быть злым"
источник
1
Если вы используете такой инструмент, как grep, который может принимать несколько выражений, разделенных символом новой строки, для сопоставления, берется декартово произведение всех возможных вариантов (например, {ab, ba} {ab, ba} становится {abba, abba, baab, баба}) достаточно, чтобы быть эквивалентным любому заданному «BRE-плюс-чередование» и, следовательно, любому регулярному языку?
Random832
1
@ Random832: попробуй сделать (abc|bac)*.
Ричи