Configuração:
- expressões regulares com referências anteriores
- idioma unário (alfabeto de 1 símbolo)
O seguinte problema é decidível nessa configuração:
- Dada uma expressão regular com referências anteriores, ela define um idioma regular?
Por exemplo, (aa+)\1define um idioma regular, enquanto (aa+)\1+não. Podemos decidir qual é o caso?
Para concretude, "expressões regulares com referências anteriores" aqui se referem, por exemplo, ao seguinte subconjunto das expressões regulares compatíveis com Perl :
acorresponde ao caracterea(o único caractere do alfabeto)X*corresponde a 0 ou mais ocorrências deXX|YjogosXouY- parênteses podem ser usados para agrupar e capturar
\1.\2, etc. correspondem à mesma sequência que o par 1, 2, etc. entre parênteses
Também podemos usar as taquigrafia normais, por exemplo X+= XX*.
formal-languages
computability
regular-languages
undecidability
regular-expressions
Jukka Suomela
fonte
fonte
Respostas:
Evidências contra a efetiva decidibilidade do problema são fornecidas pela construção da prova do Teorema 9 em meu artigo Sobre expressões regulares práticas : Você pode determinar se existem finitos primos de Fermat.
fonte