Регулярные выражения с обратными ссылками над унарным алфавитом

18

Установка:

  • регулярные выражения с обратными ссылками
  • одинарный язык (1-символьный алфавит)

В этом параметре разрешима следующая проблема:

  • Если задано регулярное выражение с обратными ссылками, определяет ли оно регулярный язык?

Например, (aa+)\1определяет обычный язык, а (aa+)\1+не -. Можем ли мы решить, какой из них имеет место?


Для конкретности «регулярные выражения с обратными ссылками» здесь относятся, например, к следующему подмножеству обычных Perl-совместимых регулярных выражений :

  • aсоответствует символу a(единственный символ в алфавите)
  • X* соответствует 0 или более вхождениям X
  • X|Yсоответствует XилиY
  • круглые скобки могут быть использованы для группировки и захвата
  • \1, \2и т. д. соответствуют той же строке, что и 1-я, 2-я и т. д. пара скобок

Мы также можем использовать обычные сокращения, например, X+= XX*.

Юкка Суомела
источник
1
|LN|

Ответы:

4

Свидетельство против эффективной разрешимости задачи обеспечивается конструкцией из доказательства теоремы 9 в моей статье « Практические регулярные выражения : вы можете определить, существует ли конечное число простых чисел Ферма».

Хольгер Петерсен
источник
Добро пожаловать на сайт! Я добавил более полную цитату к вашей статье.
Дэвид Ричерби