Estou interessado no problema clássico INCLUSÃO LÍNGUA REGULAR. Dada uma expressão regular , denotamos por L ( E ) a linguagem regular a ela associada. (As expressões regulares estão em um alfabeto fixo Σ , com a união de operações, estrela Kleene e concatenação.)
Entrada: Duas expressões regulares e E 2 Pergunta: É verdade que L ( E 1 ) ⊆ L ( E 2 ) ?
A INCLUSÃO REGULAR DA LÍNGUA é conhecida por ser completa no PSPACE [1].
O modo clássico de resolvê-lo (em PSPACE) é construir a AFNs e A 2 associada a E 1 e E 2 , para construir um DFA D 2 a partir de uma 2 , complementam-lo em um DFA D C 2 , e finalmente, construa o autômato de interseção A P a partir de A 1 e D C 2 correspondente à interseção de L ( E 1 ) e L ( E 2 ) C. Agora se e só se existe um caminho não aceitar em uma P .
Se não me engano, todo o processo pode ser feito em tempo polinomial quando é uma linguagem fixa, uma vez que o blow-up única exponencial vem transformando Um 2 em D 2 . Melhor ainda, o problema é o FPT quando parametrizado por | E 2 | , o comprimento de E 2 .
Isso motiva minha pergunta:
Pergunta: Quando é uma expressão fixa, qual é a complexidade da INCLUSÃO REGULAR DA LINGUAGEM? Ele permanece completo no PSPACE?
[1] LJ Stockmeyer e AR Meyer. Problemas de palavras que requerem tempo exponencial: relatório preliminar. Anais do quinto Simpósio anual da ACM sobre Teoria da Computação, STOC '73, pp. 1-9.
Observação: como não especialista no campo, acho [1] (e artigos relacionados da época) bastante ilegíveis e não consegui encontrar outra prova da integridade do PSPACE - qualquer ponteiro para uma prova moderna, como em um livro, é muito bem vindo! Além disso, os autores parecem permitir quadratura em suas expressões regulares, o que hoje é bastante fora do padrão, acredito.)
fonte
Respostas:
O caso particular da universalidade da linguagem (todas as palavras são aceitas?) É PSPACE-complete para expressões regulares ou NFAs. Responde à sua pergunta: em geral, o problema permanece completo no PSPACE, mesmo para fixo , pois a universalidade da linguagem corresponde a E 1 = Σ ∗ .E1 E1=Σ∗
É realmente difícil encontrar uma prova moderna de dureza PSPACE legível para a universalidade de expressões regulares, como agora é considerada folclore. Aqui está um esquema de prova rápida que permite reconstruir a prova:
Considere-se uma máquina de Turing no alfabeto Σ usando o espaço polinomial p ( n ) , e deixe w ∈ Σ * ser uma palavra de entrada para M . Construiremos uma expressão regular e que aceite todas as palavras se e somente se M não aceitar execução em w .M Σ p(n) w∈Σ∗ M e M w
[1] Sobre equivalência, contenção e cobertura de problemas para as linguagens regulares e sem contexto Harry B.Hunt, Daniel J.Rosenkrantz, Thomas G.Szymanski. Revista de Ciências da Computação e Sistemas. Volume 12, Edição 2, Abril de 1976, Páginas 222-268
[2] O problema de equivalência para expressões regulares com quadratura requer espaço exponencial . Meyer, AR e L. Stockmeyer. 13º Simpósio do IEEE sobre comutação e teoria de autômatos, outubro de 1972, pp.125-129.
fonte