Wyrażenia regularne z odniesieniami wstecznymi do jednoznacznego alfabetu

Oprawa:

• wyrażenia regularne z referencjami wstecznymi
• język jednoargumentowy (alfabet 1-symbolowy)

Czy w tym ustawieniu można rozstrzygać następujący problem:

• Biorąc pod uwagę wyrażenie regularne z odniesieniami wstecznymi, czy definiuje ono zwykły język?

Na przykład (aa+)\1definiuje zwykły język, podczas gdy (aa+)\1+nie. Czy możemy zdecydować, który jest właściwy?

Dla konkretności, „wyrażenia regularne z referencjami wstecznymi” odnoszą się tutaj np. Do następującego podzestawu zwykłych wyrażeń regularnych kompatybilnych z Perl :

• adopasowuje znak a(jedyny znak w alfabecie)
• X* dopasowuje 0 lub więcej wystąpień X
• X|Ymecze XlubY
• nawiasy mogą być używane do grupowania i przechwytywania
• \1. \2itd. pasują do tego samego łańcucha co pierwsza, druga itd. para nawiasów

Możemy również użyć normalnych skrótów, np . X+= XX*.

Dowód przeciwko skutecznej rozstrzygalności problemu dostarcza konstrukcja zawarta w dowodzie Twierdzenia 9 w moim artykule O praktycznych wyrażeniach regularnych : Można określić, czy istnieje ostatecznie wiele liczb pierwszych Fermata.