Construção do conjunto das partes

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

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 2n 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[editar | editar código-fonte]

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[editar | editar código-fonte]

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, q0, 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), q0 é 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 é {q0}, 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) | qQ}, 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 q0, 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[editar | editar código-fonte]

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.

NFA-powerset-construction-example.svg

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.

DFA-powerset-construction-example.svg

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[editar | editar código-fonte]

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 2n 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 2n 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 2n estados em um AFD, um para cada n-caractere da entrada.

Aplicação[editar | editar código-fonte]

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 2O(n log n) estados, usa construção do conjunto das partes como parte de mecanismo.

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