Установка:
- регулярные выражения с обратными ссылками
- одинарный язык (1-символьный алфавит)
В этом параметре разрешима следующая проблема:
- Если задано регулярное выражение с обратными ссылками, определяет ли оно регулярный язык?
Например, (aa+)\1
определяет обычный язык, а (aa+)\1+
не -. Можем ли мы решить, какой из них имеет место?
Для конкретности «регулярные выражения с обратными ссылками» здесь относятся, например, к следующему подмножеству обычных Perl-совместимых регулярных выражений :
a
соответствует символуa
(единственный символ в алфавите)X*
соответствует 0 или более вхождениямX
X|Y
соответствуетX
илиY
- круглые скобки могут быть использованы для группировки и захвата
\1
,\2
и т. д. соответствуют той же строке, что и 1-я, 2-я и т. д. пара скобок
Мы также можем использовать обычные сокращения, например, X+
= XX*
.
Ответы:
Свидетельство против эффективной разрешимости задачи обеспечивается конструкцией из доказательства теоремы 9 в моей статье « Практические регулярные выражения : вы можете определить, существует ли конечное число простых чисел Ферма».
источник