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.

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]