Réglage:
- expressions régulières avec références arrières
- langue unaire (alphabet à 1 symbole)
Le problème suivant est-il décidable dans ce paramètre:
- Étant donné une expression régulière avec des références arrières, définit-elle un langage régulier?
Par exemple, (aa+)\1définit une langue régulière, alors (aa+)\1+que non. Pouvons-nous décider lequel est le cas?
Pour le concret, les "expressions régulières avec des références arrières" se réfèrent ici par exemple au sous-ensemble suivant des expressions régulières compatibles Perl habituelles :
acorrespond au caractèrea(le seul caractère de l'alphabet)X*correspond à 0 occurrence ou plus deXX|YcorrespondXouY- les parenthèses peuvent être utilisées pour grouper et capturer
\1.\2, etc. correspondent à la même chaîne que la première, la deuxième, etc. paire de parenthèses
Nous pouvons également utiliser les raccourcis normaux, par exemple X+= XX*.
formal-languages
computability
regular-languages
undecidability
regular-expressions
Jukka Suomela
la source
la source
Réponses:
Des preuves contre la décidabilité effective du problème sont fournies par la construction dans la preuve du théorème 9 dans mon article sur les expressions régulières pratiques : vous pouvez déterminer s'il existe un nombre fini de nombres premiers de Fermat.
la source