Construção do conjunto das partes

Na teoria da computação e na teoria dos autômatos, a construção do conjunto das partes é um método padrão para converter autômatos finitos não-determinísticos (AFN) em autômatos finitos determinísticos(AFD) que reconheçam a mesma linguagem. Isso é importante na teoria dos autômatos pois estabelece que AFNs, apesar das duas flexibilidades adicionais, são incapazes de reconhecer alguma linguagem que não pode ser reconhecida por algo AFD. É também importante na pratica de conversão de AFNs de simples construção em AFDs de execução mais eficiente. No entanto, se o AFN tem n estados, o AFD resultado pode ter no máximo 2ⁿ estados, um número exponencialmente grande, o qual, às vezes, torna impraticável a construção de longos AFNs.

A construção, às vezes chamada de construção do conjunto das partes de Rabin-Scott para distinguir da construção similar de outros tipos de autômatos, foi primeiro publicada por M. O. Rabin and Dana Scott em 1959.

Intuição

Para simular a operação de um AFD sobre uma determinada entrada, é preciso manter o registro de cada estado a qualquer momento: o estado que o autômato vai alcançar depois de ler um prefixo da entrada. No entanto, para simular em AFN, é preciso manter o registro de um conjunto de estados: todos os estados que o autômato pode alcançar após leitura do prefixo da entrada, de acordo com a escolha feita pelo autômato não-deterministicamente. Caso, após um certo prefixo da entrada, um conjunto S de estados possam ser alcançados, então depois de próximo símbolo da entrada x o conjunto de estados alcançáveis é uma função determinística de S e x. Porem, o conjunto de estados alcançáveis no AFN segue a mesma regra em simulações de AFN assim como um único estado de um AFD roda em uma simulação de AFD, e no caso dos conjuntos do AFN encontrados na simulação pode ser reinterpretados como estados de um AFD.

Construção

A construção do conjunto das partes é aplicada mais diretamente em AFN que não permitem estados de transição sem símbolos de entrada, chamado de “Transição ε”.Como um autômato pode ser definido por uma 5-tupla(Q, Σ, T, q₀, F), na qual Q é o conjunto de estados, Σ é o conjunto de entrada, T é uma função de transição (mapeia um estado e um símbolo de entrada em um conjunto de estados), q₀ é o estado inicial e F é o conjunto de estados de aceitação. O AFD correspondente tem estados correspondentes ao subconjunto de Q. O estado inicial do AFD é {q₀}, um conjunto unitário de estados inicial. A função de transição mapeia um estado S(representando um subconjunto de Q) e um símbolo de entrada x para o conjunto T(S,x) = ∪{T(q,x) | q ∈ Q}, o conjunto de todos os estados que podem ser alcançáveis por uma x-transição a partir de um estado S. Um estado S de um AFD é um estado de aceitação se e somente se pelo menos um membro de S é um estado de aceitação do AFN.

Na versão simplificada da powerset construction, o conjunto de todos os estados do AFD é o conjunto das partes de Q, o conjunto de todas as possibilidades de subconjunto de Q. No entanto, muito estados do AFD resultante podem ser inúteis, pois pode ser inalcançáveis a partir do estado inicial. A versão alternativa da construção cria somente estados que são realmente alcançáveis. Em AFN com transições ε, a construção tem que ser modificada um pouco. Nesse caso, o estado inicial consiste em todos os estados alcançáveis no AFN por transições ε a partir de q₀, e o valor de T(S,x) na função de transições é o conjunto de todos os estados alcançáveis pela transição ε a partir de ∪{T(q,x) | q em Q}.

Também é possível que um AFN tenha mais de um estado inicial. Nesse caso, o estado inicial do AFD correspondente é o conjunto de todos os estados iniciais dos AFN, ou, no caso dos AFN tem transições ε, o conjunto de todos os estados alcançáveis a partir dos estados iniciais pela transição ε.

Exemplo

O AFN abaixo tem quatro estados: estado inicial 1 e estados de aceitação 3 e 4. Seu alfabeto consiste em dois símbolos 0 e 1, possui transições ε. O estado inicial é o estado 1.

O estado inicial do AFD construído a partir desse AFN é o conjunto de todos os estado do AFN que são alcançáveis a partir do estado 1 por transições ε; que é o conjunto {1,2,3}. A transição a partir de {1,2,3} pela entrada 0 tem que seguir a seta que parte do estado 1 para o estado 2 ou as setas que partem do estado 3 para o 4. Adicionalmente, nem estado 2 nem o estado 4 tem saída a partir de transições ε. Portanto, T({1,2,3},0) = {2,4}, e pelo mesmo raciocínio o AFD totalmente construído a partir do AFN é como está mostrado abaixo.

Como pode ser visto nesse exemplo, há 5 estados alcançáveis a partir do estado inicial do AFD; o outros 11 conjuntos restantes no conjunto das partes do conjunto do AFN são estados inalcançáveis.

Complexidade

Como os estados do AFD consistem em conjunto de estados do AFN, um AFN com n estados pode ser convertido para no máximo um AFD com 2ⁿ estados. Para cada n, existem n estados de um AFN tal que cada subconjunto de estados é alcançável a partir do subconjunto inicial, por isso o AFD convertido tem exatamente 2ⁿ estados. Um simples exemplo que requer essa quantidade de estados é a linguagem de strings sobre o alfabeto {0,1} no qual há pelo menos n caracteres, o n-ésimo caractere é 1. Ele pode ser representado por (n + 1) estados de um AFN, mas requer 2ⁿ estados em um AFD, um para cada n-caractere da entrada.

Aplicação

O algoritmo de Brzozowski para AFD minimização usa a construção do conjunto das partes duas vezes. Converte uma AFD de entrada em um AFN para a linguagem reversa, invertendo todas as setas e trocando os papéis de entrado inicial e de aceitação, converte o AFN de volta em um AFD usando novamente construção do conjunto das pastes, e então repete o processo. No pior caso, a complexidade é exponencial, diferentemente de outros algoritmos de minimização de AFD conhecidos, mas em muitos exemplos ele é mais rápido que a complexidade de pior caso sugere.

A construção de Safra, na qual converte um autômato de Büchi não determinístico com n estados em um autômato de Muller determinístico ou em um autômato de Rabin com 2^{O(n log n)} estados, usa construção do conjunto das partes como parte de mecanismo.

Referências

• Michael Sipser, Introduction to the Theory of Computation ISBN 0-534-94728-X. (See . Theorem 1.19, section 1.2, pg. 55.)
• John E. Hopcroft and Jeffrey D. Ullman, Introduction to Automata Theory, Languages, and Computation, Addison-Wesley Publishing, Reading Massachusetts, 1979. ISBN 0-201-02988-X. (See chapter 2.)
• James Andrew Anderson; Thomas J. Head (2006). Automata theory with modern applications. [S.l.]: Cambridge University Press. pp. 43–49. ISBN 9780521848879 
• Klaus Schneider (2004). Verification of reactive systems: formal methods and algorithms. [S.l.]: Springer. pp. 210–212. ISBN 9783540002963 
• M. O. Rabin and D. Scott. Finite automata and their decision problems. IBM Journal of Research and Development, 3(2):114–125, 1959