Complexidades no Teorema de Kleene

Teorema de Kleene:Para uma dada linguagem, são equivalentes

1. Ela é reconhecida por um autômato determinístico (AD)

2. Ela é reconhecida por um autômato não determinístico (AND)

3. Ela é descrita por uma expressão regular (ER)

A demonstração é por uma série de algoritmos que transformam a descrição de um tipo em descrição de outro tipo. Esta página é um guia para a complexidade desses algoritmos. Antes, é preciso definir o tamanho dos vários objetos, sugerido pelas estruturas de dados naturais:

AD: com n estados e k letras, o tamanho é nk

AND: com n estados, k letras e d transições, o tamanho é n+k+d. Entretanto, a não ser em casos patológicos, d é maior que n e k, e podemos tomar d como tamanho.

ER: existem dois tamanhos naturais para uma ER e: alf(e) é o número de ocorrências de letras do alfabeto em e; stl(e) adiciona a esse número o de ocorrências de * . Claro que alf(e) <= stl(e). Por outro lado, é sempre possível simplificar um pouco uma ER para uma forma em que stl(e) <= 2alf(e).

Vamos às transformações:

• AD para AND. É a transformação mais trivial; só muda a estrutura de dados, e é feita em tempo linear.

• AND para AD. O método é a construção dos subconjuntos, combinada com o cálculo da parte acessível. Em princípio, o número de estados pode crescer exponencialmente. Na prática, vimos, a transformação parece bem eficiente. Mas isso é só para ANDs bonzinhos. Na realidade, o número de estados pode mesmo explodir (pdf).

• ER para AD. Não existe nenhuma construção direta, tem que passar por um AND.

• ER para AND. O algoritmo de Thompson é bem eficiente. A parte inicial consiste em produzir uma árvore a partir da ER dada; isso pode ser feito em tempo linear, usando métodos de linguagens livres de contexto (a ser vistos mais à frente). A partir daí, a construção também é em tempo linear.

• AND para ER. Os algoritmos vistos parecem polinomiais. Afinal, o método das equações e substituição certamente é polinomial num contexto numérico; o método de eliminação vai fazendo as arestas desaparecerem, e só existe um número polinomial de arestas. O problema está no tamanho das expressões que aparecem como coeficientes nas equações ou como rótulos de arestas.
  Para ter uma idéia do que pode acontecer, considere um AND com n estados, 1,...,n, com uma aresta dirigida de cada estado para outro, e todos os laços; rotule cada aresta com alguma letra. Para simplificar, faça o estado 1 ser o único inicial e final. Escreva o sistema de equações correspondente, e elimine variáveis em ordem decrescente de índice. Não é dificil mostrar que, depois de eliminar t variáveis, cada coeficiente A terá alf(A) = 4ⁿ. Ou seja, o algoritmo tem espaço exponencial, e tempo idem. O método de eliminação tem comportamento semelhante.

• AD para ER. O exemplo acima funciona para AD, desde que se trabalhe com alfabetos progressivamente maiores. Mas o que acontece se fixarmos o alfabeto? E se usarmos um algoritmo melhor do que visto em aula? A resposta está num artigo recente - mesmo com um alfabeto de duas letras, existem AD com n estados tais que toda ER para sua linguagem tem alf > cⁿ, para algum c>1. O artigo é um tanto quanto difícil :-)
  Gruber, Hermann; Holzer, Markus (2008), "Finite Automata, Digraph Connectivity, and Regular Expression Size (pdf)", Proceedings of the 35th International Colloquium on Automata, Languages and Programming (ICALP 2008), pp. 39-50,doi:10.1007/978-3-540-70583-3_4

Última modificação: Mon Oct 5 17:58:06 BRT 2009 por am