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 znaka(jedyny znak w alfabecie)X*dopasowuje 0 lub więcej wystąpieńXX|YmeczeXlubY- 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*.
formal-languages
computability
regular-languages
undecidability
regular-expressions
Jukka Suomela
źródło
źródło
Odpowiedzi:
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.
źródło