Teorema de Myhill-Nerode

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa

Acerca da teoria de Linguagens Formais, o Teorema de Myhill-Nerode fornece uma condição necessária e suficiente para que uma lnguagem seja regular. O nome do teorema refere-se a John Myhill e Anil Nerode, que o provaram na Universidade de Chicago em 1958 (Nerode 1958).

Enunciado do teorema[editar | editar código-fonte]

Dada uma linguagem L e um par de cadeias x e y, defina uma extensão de distinção como sendo uma cadeia z tal que exatamente uma das duas cadeias xz e yz pertencem a L.

Defina a relação RL sobre cadeias através da regra de que x RL y se não há extensão de distinção para x e y. É fácil mostrar que RL é uma relação de equivalência sobre cadeias, e portanto divide o conjunto de todas as cadeias finitas entre classes de equivalência.

O Teorema de Myhill-Nerode afirma que L é regular se e somente se RL possui um número finito de classes de equivalência, e ainda que o número de estados no menor autômato finito determinístico (AFD) que reconhece L é igual ao número de classes de equivalência em RL. Em particular, isso implica que existe um AFD canônico único com número mínimo de estados.

Intui-se então que partindo-se de tal autômato mínimo, qualquer cadeia x e y que o leve ao mesmo estado estará na mesma classe de equivalência; e ao partir-se de uma partição das classes de equivalência, é possível facilmente construir um autômato que utiliza seu estado para rastrear as classes de equivalência contendo a parte da cadeia vista até o momento.

Prova[editar | editar código-fonte]

Se L é uma linguagem regular, então, por definição, existe um AFD A = (Q, Σ, δ, q, F) , com um número finito de estados, que o reconhece. Se existem n estados, então divida o conjunto de palavras em subconjuntos, onde o subconjunto Si é o conjunto de palavra tal que, dado Si como entrada para o AFD A, a entrada para no estado i do autômato. Para toda palavra x e y (x, y ∈ Σ*) que se encontram em um mesmo estado q (q ∈ Q), e para toda escolha de uma terceira palavra z (z ∈ Σ*) um outro estado qj pertencente ao autômato A (qj ) que é atingido por xz (palavra x concatenada com a palavra z), também é alcançado por yz (palavra y concatenada com a palavra z), portanto deve-se aceitar tanto xz quanto yz (se q ∈ F), ou rejeitá-los caso contrário (se q ∉ F). Com isso, concluímos que nenhuma palavra z pode ser uma extensão diferencial para x e y, logo, tais palavras (x e y) estão relacionadas com RL, portanto Si é um subconjunto de uma classe de equivalência de RL. Combinando este fato com o fato de que cada membro de uma dessas classes de equivalência pertence a um dos conjuntos Si, o que dá uma relação muitos (estados de A) para um(a) (classe de equivalência implicando que o número de classes de equivalência é finito e no máximo n ( n = |Q| ).

Na outra direção, suponha que RL tenha finitas classes de equivalência. Neste caso, é possível construir um autômato finito determinístico que possui um estado para cada classe de equivalência. O estado inicial do autômato corresponde a classe de equivalência contendo palavra vazia (ε), e a função de transição de um estado qk ao receber um símbolo s, leva o autômato a um novo estado, correspondente a classe de equivalência contendo a palavra xy. A definição da relação de Myhill-Nerode implica que a função de transição é bem-definida: não importa quão representativa seja a palavra x escolhida para o estado qk, o valor da função de transição será o mesmo. O estado deste autômato é de aceitação se a classe de equivalência correspondente contém uma palavra em L; neste caso, novamente, a definição de relação implica que toda palavra na mesma classe de equivalência deve também pertencer a L, caso contrário à palavra vazia seria uma distinção para alguns pares de palavras nesta classe.

Portanto, a existência de um autômato finito, o qual reconhece L, implica que a relação de Myhill-Nerode possui um número finito de classes de equivalência, no máximo igual ao numero n de estados de um autômato, e a existência de um número finito de classes de equivalência, implica que existe um autômato com n estados.

Uso e consequências[editar | editar código-fonte]

O teorema de Myhill-Nerode pode ser utilizado para mostrar que a linguagem L é regular provando-se que o número de classes de equivalência de RL é finito. Isso pode ser feito através de uma análise de caso exaustiva na qual, começando da cadeia vazia, extensões de distinção são utilizadas para encontrar classes de equivalência adicionais até que nenhuma outra possa ser encontrada. Por exemplo, a linguagem consistindo de números binários que podem ser divididos por 3 é regular. Dada a cadeia vazia, 00 (ou 11), 01 e 10 são extensões de distinção resultantes nas três classes (correspondendo aos números que resultam em resto 0, 1 e 2 quando divididos por 3), mas após essa etapa não há mais extensõe de distinção. O autômato mínimo que aceita essa linguagem teria três estados correspondendo a essas três classes de equivalência.

Outro corolário imediato do teorema é que se uma linguagem define um conjunto infinito de classes de equivalência, ela não é regular. Este é o corolário frequentemente utilizado para provar que uma linguagem não é regular.

Ver também[editar | editar código-fonte]

Referências[editar | editar código-fonte]