Autômato completo

Na definição básica de autômato finito, não é necessário que de todos os estados exista uma transição para todos os símbolos. O autômato completo é um autômato que tem transições definidas de todos os estados para todos os símbolos do alfabeto de entrada.

Como construir um autômato completo

Considere este autômato A = ⟨Q, Σ, δ, q₀, F⟩:

Aqui não está desenhada a transição do estado q₀ para a letra “b”. Se uma situação dessas ocorrer, dizemos que o autômato não aceita a palavra de entrada em questão. No entanto, do ponto de vista da formalização, pode não ser conveniente que a função de transição δ não esteja definida para alguns valores; aqui, por exemplo, ela não está definida para δ(q₀, b).

Isso se resolve com facilidade construindo um autômato equivalente com um estado a mais — para esse estado apontarão as transições “que faltam”, ele não será final e terá laços para todas as entradas seguintes. Chamamos esse autômato de autômato completo. O autômato equivalente modificado poderia ficar assim:

Acrescentamos o estado q_fail. Dos outros estados levamos uma transição até ele se, e somente se, antes não existia transição ali. Esse estado não é final e tem laços para todas as entradas seguintes. Onde, no autômato anterior, esbarraríamos em uma transição que faltava, aqui não falta nenhuma transição, e o autômato vai parar no estado q_fail.

Sempre podemos, portanto, sem perda de generalidade, supor que o autômato tem transições definidas para todas as combinações de estados e caracteres do alfabeto.

Definição

Para um autômato completo A = ⟨Q, Σ, δ, q₀, F⟩ vale, portanto, que

$$\mathrm{\forall }q\in Q\mathrm{\forall }a\in \mathrm{\Sigma }\mathrm{\exists }r\in Q:\delta (q,a)=r.$$

Fontes

• M. Sipser: Introduction to the Theory of Computation
• Aho, Sethi, Ullman: Compilers: Principles, Techniques, and Tools