Algoritmo para testar se um idioma é regular

Existe um algoritmo / procedimento sistemático para testar se um idioma é regular?

Em outras palavras, dado um idioma especificado em forma algébrica (pense em algo como ), teste se o idioma é regular ou não. Imagine que estamos escrevendo um serviço da Web para ajudar os alunos com todos os seus trabalhos de casa; o usuário especifica o idioma e o serviço da web responde com "regular", "não regular" ou "não sei". (Gostaríamos que o serviço da Web respondesse "não sei" com a menor frequência possível.) Existe alguma boa abordagem para automatizar isso? Isso é tratável? É decidível (ou seja, é possível garantir que nunca precisamos responder "eu não sei")? Existem algoritmos razoavelmente eficientes para resolver esse problema e poder fornecer uma resposta diferente de "não sei" $L=\{a^n b^n : n \in \mathbb{N}\}$

O método clássico para provar que um idioma não é regular é o lema de bombeamento. No entanto, parece que requer uma percepção manual em algum momento (por exemplo, para escolher a palavra a ser bombeada), então não estou claro se isso pode ser transformado em algo algorítmico.

Um método clássico para provar que uma linguagem é regular seria usar o teorema de Myhill-Nerode para derivar um autômato de estado finito. Isso parece uma abordagem promissora, mas requer a capacidade de executar operações básicas em idiomas na forma algébrica. Não está claro para mim se existe uma maneira sistemática de executar simbolicamente todas as operações que possam ser necessárias, em idiomas de forma algébrica.

Para tornar essa questão bem formulada, precisamos decidir como o usuário especificará o idioma. Estou aberto a sugestões, mas estou pensando em algo assim:

L = {E : S}

$L = \{E : S\}$

onde é uma expressão de palavra e é um sistema de desigualdades lineares sobre as variáveis de comprimento, com as seguintes definições: $E$ $S$

Cada um de é uma expressão de palavra. (Eles representam variáveis que podem assumir qualquer palavra em .) $x,y,z,\dots$ $\Sigma^*$
Cada um de é uma expressão de palavra. (Aqui representa o reverso da cadeia .) $x^r,y^r,z^r,\dots$ $x^r$ $x$
Cada de é uma expressão de palavra. (Implicitamente, , então representam um único símbolo no alfabeto subjacente.) $a,b,c,\dots$ $\Sigma=\{a,b,c,\dots\}$ $a,b,c,\dots$
Cada de é uma expressão de palavra, se é uma variável de comprimento. $a^\eta,b^\eta,c^\eta,\dots$ $\eta$
A concatenação de expressões de palavras é uma expressão de palavras.
Cada um de é uma variável de comprimento. (Eles representam variáveis que podem assumir qualquer número natural.) $m,n,p,q,\dots$
Cada um de É uma variável de comprimento. (Eles representam o comprimento de uma palavra correspondente.) $|x|,|y|,|z|,\dots$

Isso parece amplo o suficiente para lidar com muitos dos casos que vemos nos exercícios de livros didáticos. Obviamente, você pode substituir qualquer outro método textual de especificar um idioma na forma algébrica, se tiver uma sugestão melhor.

Ainda não tive tempo de pensar muito em sua escolha de expressões de linguagem. Aproximadamente que tipos de idiomas ele abrange? Se você adicionar a restrição de que uma variável de palavra ocorra apenas uma vez, todos esses idiomas não têm contexto?

Gilles 'SO- stop be evil' (

Talvez você possa tentar escrever o próprio

com uma gramática? Como e, é sucintamente o que você descreve?

E

$E$

E ::= c^{η} ∣ x ∣ E E ∣ E^{r}

$E ::= c^η ∣ x ∣ EE ∣ E^r$

η ::= n ∣ | x |

$η ::= n ∣ |x|$

Jmad

Você pode expressar para que isso vá muito além das linguagens sem contexto. Ainda assim, suspeito que o problema seja pelo menos tão difícil quanto decidir se uma gramática sem contexto define uma linguagem comum.

{a^{n} b^{n} c^{n} ∣ n \in N}

$\{a^nb^nc^n \mid n\in\mathbb{N}\}$

Gilles 'SO- stop be evil'

@ jmad, sim, isso seria perfeitamente razoável. Eu não estou apegado a essa escolha de expressões de linguagem: fique à vontade para escolher outra coisa, se você vir outra coisa mais apropriada. Gilles, ótimo ângulo de ataque! (Para os espectadores, existem resultados conhecidos que mostram que testar se uma gramática arbitrária e livre de contexto define um idioma regular é indecidível.) Se o problema for indecidível, sugiro que o alteremos para permitir que o serviço da Web responda "Eu não não sei "e peça um algoritmo que responda" não sei "o mais raramente possível.

Esta aula não está fechada com a estrela Kleene, está? Você pode expressar parênteses equilibrados?

Gilles 'SO- stop be evil'

Respostas:

A resposta é não. Decidir se uma determinada gramática sem contexto gera uma linguagem regular é um problema indecidível.

Update . Eu dei essa resposta negativa à pergunta geral

Dado um idioma especificado em forma algébrica, teste se o idioma é regular ou não

uma vez que linguagens livres de contexto são soluções de equações algébricas em linguagens: veja o Capítulo II, Teoremas 1.4 e 1.5 no livro de J. Berstel Transductions and Context-Free Languages .

No entanto, a mesma pergunta é decidível para linguagens determinísticas livres de contexto, um resultado não trivial devido ao Stearns [1] e aprimorado pelo Valiant [2]:
[1] RE Stearns, um teste de regularidade para máquinas de empilhamento , informações e controle 11 323- 340 (1967). DOI: 10.1016 / S0019-9958 (67) 90591-8.
[2] LG Valiant. Regularidade e problemas relacionados ao autômato de empuxo determinístico J. ACM 22 (1975), pp. 1–10.

Há outro resultado positivo, mais próximo das especificações fornecidas na segunda parte da pergunta. Lembre-se de que os subconjuntos semilineares de são exatamente os conjuntos definíveis na aritmética do Presburger. Existem também os subconjuntos racionais de . Em particular, um subconjunto de definido por inequações lineares é racional. Agora, dado um subconjunto racional de , é decidível se o idioma é regular. De fato, sabe-se [Ginsburg-Spanier] que é regular se e somente se é um subconjunto reconhecível de $\mathbb{N}^k$ $\mathbb{N}^k$ $\mathbb{N}^k$ $R$ $\mathbb{N}^k$

eu (R) = {{você}_{1}^{n_{1}} \dots {você}_{k}^{n_{k}} ∣ (n_{1}, . . ., n_{k}) \in R}

$L(R) = \{ u_1^{n_1} \dotsm u_k^{n_k} \mid (n_1, ...,n_k) \in R \}$

L (R)

$L(R)$

R

$R$

N^{k}

$\mathbb{N}^k$ e é decidido [Ginsburg-Spanier] se um determinado subconjunto racional de é reconhecível.

N^{k}

$\mathbb{N}^k$

S. Ginsburg e EH Spanier., Semigroups, Presburger fórmulas e idiomas , Pacific J. Math. 16 (1966), 285-296.

S. Ginsburg e EH Spanier. Conjuntos regulares limitados , Proc. da matemática americana. Soc. 17 , 1043-1049 (1966).

Isso não resolve a segunda parte da pergunta, que pode ser indecidível por causa da palavra variáveis, mas fornece um fragmento razoável para começar.

J.-E. PIN
fonte

(a) Pedante nit: Não está claro para mim se a sintaxe algébrica acima é geral o suficiente para expressar todas as gramáticas sem contexto (como Gilles e eu sugerimos nos comentários), portanto, não está totalmente claro se esse resultado específico se aplica aqui . (b) Mais importante: considere a declaração do problema adequadamente ajustada para que o serviço da Web possa responder "Não sei" e gostaríamos de encontrar um algoritmo que responda "Não sei" tão raramente que possível. Eu sugeri isso anteriormente nos comentários; Vou editar a pergunta para tornar isso mais claro na própria pergunta.

Eu suspeito que você pode adaptar a prova, mas o resultado não segue. Eu acho que existem linguagens sem contexto que não podem ser expressas nesse formalismo: por exemplo, como você expressa parênteses equilibrados? A classe de idiomas não está fechada sob a estrela Kleene, está?

Gilles 'SO- stop be evil'

@ Gilles, sim, eu pensei sobre isso. Não está imediatamente claro para mim como adaptar a prova. A prova padrão de que é indecidível dizer se uma gramática livre de contexto é regular é pelo teorema de Greibach. No entanto, não me parece que essa classe de linguagens satisfaça as premissas do teorema de Greibach (não parece provável que ela seja fechada sob concatenação com conjuntos regulares e fechada sob união). Talvez haja alguma outra abordagem de prova com a qual eu não esteja familiarizado. Concordo, não está claro como expressar a linguagem dos parênteses equilibrados nesta forma algébrica.

Acabei de adicionar as referências.

J.-E.

Sua postagem não responde à pergunta, porque aborda uma classe de idiomas diferente. As formas algébricas permitidas aqui (com uma única expressão de palavra) não são (até onde sabemos) tão gerais quanto as formas algébricas necessárias para expressar linguagens arbitrárias e livres de contexto. Pode ser que, para a interseção dos dois, o problema seja decidido.

Gilles 'SO- stop be evil'