Prévia do material em texto

Autômatos finitos determinísticos
Apresentação
Ao se falar de computação, remete-se imediatamente à ideia de um computador atrelado a 
recursos avançados. Mas o que é um computador? O conceito de computador é complexo e 
baseado em abstrações matemáticas formais chamadas de "modelos computacionais". O modelo 
computacional é a representação de máquinas por meio de um computador teórico ou não, que 
busca destacar somente detalhes relevantes.
Em teoria da computação, há alguns modelos computacionais, dos mais simples aos mais 
complexos. Há um tipo de modelo computacional extremamente simples, com memória limitada e 
restrita a somente seus estados: o autômato finito determinístico (AFD), ou máquina de estados 
finitos. O AFD faz parte da classe das linguagens regulares e aceita/rejeita sequências de símbolos, 
gerando uma sequência única de computação de acordo com a cadeia inserida na entrada.
Nesta Unidade de Aprendizagem, você vai conhecer o conceito, as características, a formalização, 
as operações (união, concatenação e estrela) e a ideia de minimização de AFDs. Verá a utilização de 
autômatos por meio dos diagramas e tabela de mapeamentos dos estados-transições, em que é 
possível trabalhar os conceitos de símbolos, alfabeto, cadeias aceitas e rejeitadas, estados, estados 
iniciais e finais.
Bons estudos.
Ao final desta Unidade de Aprendizagem, você deve apresentar os seguintes aprendizados:
Definir a classe dos autômatos finitos determinísticos.•
Exemplificar a construção de autômatos finitos determinísticos.•
Desenvolver o algoritmo de minimização de autômatos finitos determinísticos.•
Infográfico
O autômato finito determinístico surgiu com muitos objetivos, entre eles a capacidade de 
reconhecer uma linguagem. É importante destacar que uma linguagem é formada por suas cadeias, 
que, por sua vez, determinam e expressam um conjunto de regras que delimitam o escopo destas. A 
título de exemplificação, pode-se dizer que as cadeias "xy", "xxyy", "xxxyyy", e assim por diante, 
pertencem à linguagem que é formada por cadeias que começam por x, tendo a mesma quantidade 
de x e y.
No Infográfico a seguir, você verá a classificação das linguagens formais, entre elas a linguagem 
regular, que é usada no autômato finito determinístico.
Conteúdo interativo disponível na plataforma de ensino!
 
Conteúdo do Livro
Os autômatos finitos determinísticos são modelos computacionais extremamente importantes em 
linguagens formais e autômatos e apresentam grande utilização e representação na ciência da 
computação. Dessa forma, constituem-se em um dos formalismos das linguagens regulares.
No capítulo Autômatos finitos determinísticos, base teórica desta Unidade de Aprendizagem, você 
aprenderá os conceitos de computador e modelos computacionais e a sua relação com os AFDs. 
Além disso, verá o conceito um AFD, seu algoritmo de otimização de AFD e os passos de uma 
computação a partir de uma cadeia.
Boa leitura.
LINGUAGENS 
FORMAIS E 
AUTÔMATOS
OBJETIVOS DE APRENDIZAGEM
 > Definir a classe dos autômatos finitos determinísticos.
 > Exemplificar a construção de autômatos finitos determinísticos.
 > Desenvolver o algoritmo de minimização de autômatos finitos determi-
nísticos.
Introdução
O autômato finito determinístico (AFD), ou máquina de estado finita, é uma 
abstração matemática de modelos computacionais teóricos-formais que utilizam 
uma quantidade de memória extremamente restrita e pequena em relação às 
aplicações dos modelos computacionais modernos (LEWIS; PAPADIMITRIOU, 
2004). Nos AFDs, é gerado apenas um único ramo de computação para cada 
cadeia fornecida na entrada. Isto se dá por meio da rejeição ou aceitação das 
cadeias formadas pelos símbolos disponíveis nas transições entre os estados 
finitos e pré-definidos dos autômatos (SIPSER, 2007). É importante salientar 
que os AFDs são reconhecedores eficientes de linguagens regulares (HOPCROFT; 
MOTWANI; ULLMAN, 2003).
Os aspectos que caracterizam os AFDs podem ser vistos a seguir: deter-
minismo dos símbolos e estados, um único estado inicial para o autômato, 
função de transição total para qualquer cadeia fornecida para ser aceita ou 
não, muitos estados de aceitação e um conjunto finito de estados em que 
acontecerão as transições.
Autômatos finitos 
determinísticos
Leonardo Brendo Gomes Nascimento
Neste capítulo, você vai conhecer o conceito, os componentes, as carac-
terísticas, a formalização, as operações (união, concatenação e estrela) e a 
ideia de minimização de AFDs. É exemplificada a utilização de autômatos por 
meio dos diagramas e das tabelas de mapeamentos dos estados-transições, 
nos quais será possível trabalhar os conceitos de símbolos, alfabeto, cadeias 
aceitas e rejeitadas, estados, estados iniciais e estados finais.
Conceituando o autômato finito 
determinístico 
Para entender o que é AFD, faz-se necessário compreender o que é um autômato 
em si. A ideia de autômato surgiu a partir da necessidade de representação de 
um computador. No entanto, a idealização de um computador é muito complexa, 
por isso utiliza-se um computador idealizado chamado de modelo computacional 
para representar somente os detalhes pertinentes para se fazer uma formaliza-
ção teórica ou não (SIPSER, 2007). Na teoria da computação há muitos tipos de 
modelos computacionais; o mais simples deles, com memória extremamente 
limitada, é escopo de atuação restrita e chamado de máquina de estados finitos 
ou autômatos finitos, podendo ser visualizado na Figura 1. É considerado uma 
máquina formada por três componentes, a saber (MENEZES, 2011):
 � fita: mecanismo que contém as informações de entradas que serão 
processadas;
 � unidade de controle: estrutura que representa o estado atual da 
máquina, possuindo uma unidade responsável por fazer a leitura, 
acessando uma célula da fita por vez, no sentido único da esquerda 
para a direita da fita;
 � função de transição: mecanismo responsável por estabelecer as lei-
turas e definir o estado da máquina de acordo com a informação de 
entrada da fita.
Figura 1. Autômato finito representado por uma máquina contendo estados finitos.
Fonte: Menezes (2011, p. 70).
Autômatos finitos determinísticos2
O autômato finito, por sua vez, está dividido entre (MENEZES, 2011):
 � determinístico (AFD): neste tipo de autômato, o sistema chega em um 
único estado bem determinado, a partir do estado atual e do símbolo 
lido/consumido na entrada da fita;
 � não determinístico (AFN): neste tipo de autômato, o sistema pode 
chegar a um estado que está contido em uma coleção de estados, 
a partir do estado atual e do símbolo lido/consumido na entrada da fita.
Este capítulo está dedicado somente ao estudo dos AFDs. Como já men-
cionado anteriormente, os AFDs têm pouca memória e com isso os compu-
tadores que estes vão representar também são restritos, podendo realizar 
atividades que exijam pouca memória. Neste momento, o caro leitor pergunta 
o que se pode fazer com um computador que possui memória extremamente 
limitada? Muitas coisas em nosso cotidiano, pois esse tipo de computador é 
usado o tempo todo em vários dispositivos eletromecânicos, como o sistema 
lógico para controlar um elevador, o regulador usado em ar-condicionado e 
o controlador para porta automática. Para fins de explicação, será utilizado 
o exemplo do controlador para uma porta automática, com a finalidade de 
trazer uma abordagem inicialmente prática do AFD. A Figura 2 apresenta a 
visão superior do controlador para uma porta automática que abre/fecha de 
acordo com a aproximação de algum objeto detectado pelo sensor.
Figura 2. Porta lógica que abre/fecha de acordo 
com a aproximação de algum objeto/corpo.
Fonte: Adaptada de Sipser (2007).
Autômatos finitos determinísticos 3
Conforme pode ser visto na Figura 2, tem-se uma situação que pode ser 
modelada como um AFD. Essa situação envolve um controlador de porta 
automática que possui um tapete à sua frente e outro na sua dianteira. Esse 
dispositivo é geralmente utilizadoem entradas e saídas de shoppings, lojas, 
supermercados e outros estabelecimentos. Esse tipo de porta abre e fecha 
automaticamente à proporção que a pessoa ou objeto se aproxima. Trazendo 
para a realidade de AFD, pode-se elencar os estados e os símbolos (condições) 
que promovem o bom funcionamento do controlador da porta automática, 
a saber:
 � estados: aberta e fechada;
 � símbolos: (1) frente (pessoa ou objeto está se aproximando da frente 
da porta); (2) atrás (pessoa ou objeto está na traseira porta); (3) ambos 
(condições 1 e 2 simultaneamente); e (4) nenhum (negação das condições 
1 e 2 simultaneamente). 
A representação gráfica da modelagem do controlador da porta automá-
tica é apresentada a seguir, na Figura 3, por meio do diagrama de estados 1. 
Pode-se ver, no Quadro 1, os estados sendo alcançados por meio do consumo 
dos símbolos.
Figura 3. Diagrama de estados do controlador da porta 
automática. 
Quadro 1. Estados e símbolos do controlador da porta automática 
Símbolos
Nenhum Frente Atrás Ambos
Estados
Fechada Fechada Aberta Fechada Fechada
Aberta Fechada Aberta Aberta Aberta
Autômatos finitos determinísticos4
Conforme pode-se ver na Figura 3, o estado é representado por um círculo 
e consome um símbolo, que pode ir para si mesmo ou para outro estado. 
No exemplo da Figura 3, quando o estado fechado consome o símbolo nenhum, 
ele vai continuar fechado; quando consome o símbolo frente, vai ao estado 
aberto e assim por diante no outro estado, de acordo com as possibilidades 
fornecidas pela quantidade de símbolos; quanto mais símbolos, mais tran-
sições haverá. O Quadro 1 mostra todas as possibilidades de transições que 
este AFD realiza durante o processo de abrir e fechar da porta automática 
por meio do controlador.
Observe que diante da situação da porta automática, é necessário tomar 
uma decisão, para que assim o controlador da porta seja acionado e realize 
a ação correta, abrindo ou fechando. Neste contexto é importante salientar 
que a decisão realizada pelo mecanismo vai determinar a ação que deve 
executar. Ainda sobre o exemplo da porta automática, uma decisão que ela 
deve tomar é abrir ou fechar — abrir quando alguém se aproximar; fechar 
quando não há aproximação. Com isso, surgem alguns detalhes que vão ser 
especificados nos AFDs.
O AFD busca estabelecer que uma informação pode pertencer, ou não, 
a um padrão ou grupo de informações. A informação é chamada de cadeia 
(conjunto de símbolos) e o padrão ou grupo de informações de linguagem, que, 
por sua vez, contém muitas cadeias. Para que uma cadeia venha a pertencer 
a uma linguagem, faz-se necessário que obedeça aos critérios da linguagem; 
traduzindo, para o AFD, uma cadeia será aceita quando seu último símbolo 
for consumido no estado de aceitação. 
O AFD possui um conjunto de estados; dentre eles, só há um inicial, 
no qual o autômato começa seu processamento da entrada e pode ter vários 
de aceitação. O estado de aceitação, ou final, é a estrutura responsável por 
indicar se uma cadeia deve ou não ser rejeitada por uma linguagem: se o 
último símbolo da entrada for utilizado neste, dizemos que esta cadeia deve 
ser aceita. Mas o que seria o símbolo? O símbolo é uma entrada de dados 
contido em um conjunto de símbolos chamado de alfabeto da linguagem. É 
importante destacar que o símbolo é usado para expressar as demais palavras 
do alfabeto, inclusive a vazia, denotado pela letra grega épsilon (ε).
A ideia inicial de AFD já foi introduzida, então, a seguir é apresentada a 
resolução de um exercício para fixação do conteúdo estudado até o momento. 
De acordo com a Figura 4 e o Quadro 2, pode-se ver o AFD que será resolvido 
e suas possibilidades de transições. Desenvolva o AFD por meio do diagrama 
de estados que aceite somente cadeia que contenha no mínimo três 1, em 
Autômatos finitos determinísticos 5
seguida esboce a tabela dos estados e símbolos. Observação: os símbolos 
que podem ser utilizados são 1 e 0.
Figura 4. Diagrama de estados do AFD que aceita somente 
cadeias que tenha no mínimo três 1.
Quadro 2. AFD que aceita somente cadeias que tenha no mínimo três 1
Símbolos — 0 1
Estados
q0 (estado inicial) q0 (estado inicial) q1
q1 q1 q2
q2 q2 q3
q3 (estado final) q3 (estado final) q3 (estado final)
Conforme pode-se ver na Figura 4 e no Quadro 2, há quatro estados 
(q0, q1, q2 e q3) e os dois símbolos (0 e 1) que são consumidos entre os estados. 
Diferente do diagrama apresentado na Figura 3, o diagrama da Figura 4 tem 
alguns recursos gráficos diferentes que desempenham um papel importante. 
O primeiro recurso gráfico diferente é o aplicado ao estado q0; este tem um 
triângulo apontando para si, então, por conversão, este é o estado inicial do 
AFD. O segundo recurso gráfico diferente é o aplicado ao estado q3, que tem 
um círculo menor dentro do círculo que representa o estado q3, então, por 
conversão, este é o estado final ou de aceitação do AFD.
No tocante à resolução deste exercício, é preciso assegurar que haverá 
no mínimo três 1s, independentemente das posições dos 1s. A estratégia 
para resolver esse problema é encadear o consumo de três 1s entre quatro 
estados. No quarto e último estado, pode-se colocá-lo como o estado de 
aceitação, em seguida, o consumo do outro símbolo. A seguir são mostradas 
cadeias que devem ser aceitas e rejeitadas por este AFD.
Autômatos finitos determinísticos6
 � Cadeias aceitas: 111, 0101010, 1110001, 0001110, 100000000000011 e 
11111111110000001.
 � Cadeias rejeitadas: 000, 0101000, 0010001; 1100;10000000000000001 
e 10000001.
Até o presente momento do estudo foram vistas somente as estruturas 
chamadas de estados e símbolos, sendo rapidamente falado de transições. 
Mas o AFD teria outras estruturas além dessas? Sim, e serão vistas na for-
malização do AFD, disposta na subseção a seguir.
Formalização do autômato finito determinístico 
Embora expressar o AFD por meio dos exemplos vistos nos diagramas e tabelas 
seja interessante e intuitivamente didático, pode deixar a definição do que 
se deseja explicar evasiva e com muitas dúvidas, pois exemplos não são uma 
generalização, mas casos isolados e específicos do que seja um AFD. Desta 
forma, é necessário usar a definição formal, por duas razões. A primeira é 
que uma definição formal é precisa, por exemplo, caso seja necessário saber 
se um AFD poderia ter vários estados de aceitação, ou se poderia ter mais de 
um estado inicial. Por meio da consulta à definição formal, saberíamos que 
a primeira assertiva é verdadeira e a segunda é falsa. A segunda razão é que 
a definição formal viabiliza notação. Boas notações chegam muito próximo 
da generalização dos casos que se desejam trabalhar, ajudando a pensar e 
expressar as ideias claramente, pois a notação conduz um significado em 
volta dos objetos utilizados em sua formação. Por fim, a formalização do AFD 
pode ser vista por meio de uma 5-upla (Q, Σ, δ, q0, F) (HOPCROFT; MOTWANI; 
ULLMAN, 2003; SIPSER, 2007; MENEZES, 2011):
 � Q é um conjunto finito e pré-definido de estados;
 � Σ é um conjunto finito de símbolos chamado de alfabeto;
 � δ: Q × Σ → Q é a função de transição ou computação;
 � q0 ∈ Q é o estado inicial utilizado;
 � F ⊆ Q é o conjunto de estados de aceitação. Logicamente, a quantidade 
de estados finais não pode ser maior que a quantidade dos estados 
do autômato em questão.
Autômatos finitos determinísticos 7
Sobre os AFDs, é necessário levar em considerar que: (1) todas as palavras 
são finitas, (2) um AFD sempre vai parar e (3) todo símbolo é consumido e 
processado a cada função de transição. A última consideração origina a função 
de transição estendida, ou computação. A partir do diagrama apresentado 
na Figura 5, que aceita a linguagem L1, pode-se ver, conforme o Quadro 3, 
os itens da formalização de um AFD.
Figura 5. Diagrama de estados usado para exemplificar 
a computação M1 no AFD.
Pode-se expressar M1 formalmente escrevendo M1 = (Q, Σ, δ, q0, F), onde:
 � Q = {q0, q1 e q2},
 � Σ = {a, b},� δ é desenhada como exemplificado no Quadro 3:
Quadro 3. Exemplificação da computação da M1 no AFD
a b
q0 q0 q1
q1 q2 q1
q2 q1 q1
 � q0 é o estado inicial;
 � F = {q1}.
Autômatos finitos determinísticos8
Formalização de computação em um autômato 
finito determinístico 
Desta forma, considere M = (Q, Σ, δ, q0, F) um AFD. O processo de computa-
ção de M é definido por uma extensão da função de transição δ: Q × Σ para 
palavras, representada por δ*: Q × Σ*→ Q e chamada de função de transição 
estendida. Essa função é definida de forma indutiva: (HOPCROFT; MOTWANI; 
ULLMAN, 2003; SIPSER, 2007; DIVERIO; MENEZES, 2011):
δ*(q, ε) = q (a) (base da indução)
δ*(q, aw) = δ*(δ(q, a), w) (b) (passo da indução)
Conforme pode-se ver, a evolução de (a) chegando a (b) foi por meio das 
contínuas sucessões de aplicações da função de transição estendida para 
cada símbolo consumido da cadeia fornecida, sendo a um símbolo prefixo 
qualquer da palavra w. A seguir você verá um exemplo da aplicação da função 
de transição estendida. Desenvolva o resultado da computação da palavra 
00 a partir de q0:
δ*(q0, 00) = função estendida sobre 00,
δ*(δ(q0, 0), 0) = processo 00,
δ*(q1, 0) = função estendida sobre 0,
δ*(δ(q1, 0), ε) = processo 0,
δ*(qf, ε) = qf função estendida sobre ε.
Considere M = (Q, Σ, δ, q0, F) um AFD e w = w1w2 … wn uma sequência de 
caracteres, de forma que wi pertence a Σ. Então pode-se dizer que M aceita 
w caso exista uma cadeia de estados r0, r1, r2 … rn que pertença a Q com três 
condições, a saber (SIPSER, 2007):
 � r0 = q0: isto significa que a máquina sempre vai começar no estado 
inicial;
 � δ(ri, wi+1) = ri+1: isto significa que a máquina alcança outros estados a 
partir da execução da função de transição;
 � rn pertence a F: isto significa que a máquina só aceita a sequência se 
a execução da função de transição chegar ao estado de aceitação.
Autômatos finitos determinísticos 9
Entendidas as três condições anteriores, a seguir é apresentado um pro-
blema para fixação da formalização da computação por meio de um AFD 
esboçado pelo Quadro 4. Tenha que o AFD é do formato M1 = ({q0, q1, q2, qf}, 
{0,1}, δ1, q0,{qf}).
Quadro 4. Exemplificação da função de transição δ1
Símbolos - 0 1
Estados
q0 q1 q2
q1 qf q2
q2 q1 qf
qf qf qf
Desenvolva o resultado da computação da palavra 0100 a partir de q0, 
mostrando cada símbolo sendo consumido e o seu diagrama.
Aplicando a função de transição na palavra 0100 a partir de q0, tem-se:
 � δ*(q0, 0100) = função estendida sobre 0100,
 � δ*(δ(q0, 0) ,100) = processo 0100,
 � δ*(q1, 100) = função estendida sobre 100,
 � δ*(δ(q1, 1), 00) = processo 100,
 � δ*(q2, 00) = função estendida sobre 00,
 � δ*(δ(q2, 0), 0) = processo 00,
 � δ*(q1, 0) = função estendida sobre 0,
 � δ*(δ(q1, 0), ε) = processo 0,
 � δ*(qf, ε) = qf função estendida sobre ε.
A Figura 6 representa o diagrama da computação M1 e pode-se concluir que 
a palavra 0100 é aceita por este AFD, pois após o consumo do último símbolo, 
o estado alcançado foi o estado de aceitação. Fique atento à definição formal 
do AFD, pois a partir desta formalização as dúvidas e incertezas dos exemplos 
sobre as propriedades deste tipo de autômato podem ser dirimidas. É importante 
destacar que cada componente da 5-upla cumpre um papel indispensável, sendo 
possível estabelecer o autômato a partir das cinco informações dispostas na 
formalização. Muita atenção à função de transição, pois esta costuma ser a 
parte mais complexa do AFD.
Autômatos finitos determinísticos10
Figura 6. Diagrama de estados usado para exemplificar 
a computação M1 no AFD.
Implementando autômatos finitos 
determinísticos por meio dos diagramas 
e tabelas
A seguir serão realizados exercícios envolvendo AFDs para fixação do con-
teúdo. Esta seção busca ativamente aprofundar os conhecimentos por meio 
de outros exemplos. Cada exercício será composto por duas partes, a saber: 
problema e resposta.
Problema 1
 L(Ma) = {w ∈ (0, 1)* | |w| > 0 e w termina com 1}. Exemplos de cadeias aceitas 
por essa linguagem: 1, 01, 11, 001, 011, 101.... Esboce o diagrama de estados e 
a construção formal do AFD que reconheça esta linguagem. A Figura 7 apre-
senta a figura do AFD que reconhece a L(Ma) e o Quadro 5 ilustra os estados 
e transições utilizados na L(Ma) .
Resposta 1
 � Q = {q0 e q1};
 � Σ = {0, 1};
 � δ é desenhada conforme exemplificado no Quadro 5.
Autômatos finitos determinísticos 11
Quadro 5. Transições do AFD da L(Ma)
0 1
q0 q0 q1
q1 q0 q1
 � q0 é o estado inicial;
 � F = {q1}.
Figura 7. Diagrama de estados AFD do L(Ma).
Problema 2
L(Mb) = {w ∈ (0, 1)* | w não termina com 1}. Exemplos de cadeias aceitas por 
essa linguagem: 10, 010, 110, 0110, 1010, 1000.... Esboce o diagrama de esta-
dos e a construção formal do AFD que reconheça esta linguagem. A Figura 8 
apresenta o AFD que reconhece a L(Ma) e o Quadro 6 dispõe das transições 
utilizadas no AFD em questão.
Resposta 2
Figura 8. Diagrama de estados AFD do L(Mb).
 � Q = {q0 e q1},
 � Σ = {0, 1},
 � δ é desenhada como no Quadro 6:
Autômatos finitos determinísticos12
Quadro 6. Transições do AFD da L(Mb)
0 1
q0 q0 q1
q1 q0 q1
 � q0 é o estado inicial;
 � F = {q0}.
Problema 3
L(Mc) = {w ∈ (0, 1)* | |w| > 0 e w começa e termina o mesmo símbolo}. Exemplos 
de cadeias aceitas por essa linguagem: 1, 0, 11, 00, 1001, 0110.... Esboce o 
diagrama de estados e a construção formal do AFD que reconheça esta lin-
guagem. A Figura 9 mostra o AFD que reconhece a L(Mc) e o Quadro 7 apresenta 
as transições necessárias para o AFD em questão.
Resposta 3
Figura 9. Diagrama de estados AFD do L(Mc).
 � Q = {s, r1, r2, q1 e q2},
 � Σ = {0, 1},
 � δ é desenhada como:
Autômatos finitos determinísticos 13
Quadro 7. Transições do AFD da L(Mc)
0 1
s q1 r1
r1 r2 r1
r2 r2 r1
q1 q1 q2
q2 q1 q2
 � s é o estado inicial;
 � F = {r1, q1}.
Problema 4
L(Md) = {w ∈ (0, 1)* | w contém a subcadeia 001}. Exemplos de cadeias aceitas por 
essa linguagem: 1001, 0110, 10011, 00001, 1000101, 0100110.... Esboce o diagrama 
de estados e a construção formal do AFD que reconheça esta linguagem. A 
Figura 10 apresenta o AFD que reconhece a L(Md) e o Quadro 8 apresenta as 
transições utilizadas no AFD em questão.
Resposta 4
Figura 10. Diagrama de estados AFD do L(Md).
 � Q = {q0, q1, q2, q3},
 � Σ = {0, 1},
 � δ é desenhada como:
Autômatos finitos determinísticos14
Quadro 8. Transições do AFD da L(Md)
0 1
q0 q1 q0
q1 q2 q0
q2 q2 q3
q3 q3 q3
 � q0 é o estado inicial;
 � F = {q3}.
Uma linguagem pode ter vários AFDs que a reconheçam, possibilitando 
assim múltiplas respostas, desde que atendam as especificações estabeleci-
das. No entanto, há soluções que envolvem mais estados para um problema 
que nem sempre exige muitos estados. Desta forma, existe a possibilidade de 
melhorar um AFD, reduzindo-o para um AFD mais otimizado e com o mesmo 
poder de representação. Na seção a seguir será visto como acontece tal 
mecanismo.
Otimizando o autômato finito 
determinístico 
A estratégia principal aplicada por meio do algoritmo de minimização é 
determinar quais estados de um AFD possuem equivalência, isto é, que se 
comportam identicamente ao consumir um símbolo ou não. Por definição, se 
dois estados X e Y possuem equivalência, então o resultado final (aceitação 
ou rejeição) do processamento de qualquer cadeia w ∈ Σ* deve ser igual se 
iniciado a partir de X ou a partir de Y. Formalmente dois estados possuem 
equivalência se ∀w ∈ Σ*: w é aceita a partir X e ⇔ w é aceita a partir Y (HOP-
CROFT; MOTWANI; ULLMAN, 2003).
A minimização do autômato une os estados equivalentes entre si, não 
alterando o seu funcionamento, visto que estados equivalentes têm o compor-
tamento idêntico para toda cadeia. Em relação aos estados que não possuem 
equivalência, estes não devem ser unidos e permanecem separados (SIPSER, 
2007; MENEZES, 2011). Algumas observações sobre a minimização dos AFDs 
estão listadas a seguir:
Autômatos finitos determinísticos 15
 � Neste mecanismo,o conjunto de estados Q é particionado entre o 
bloco dos estados finais F e dos estados não-finais Q – F.
 � Nenhum estado contido em F pode ser equivalente a algum estado de 
Q – F, pois a cadeia p ∈ Σ* é reconhecida a partir de qualquer estado 
pertencente a F, mas rejeitada a partir de qualquer estado contido em 
Q – F. Em seguida, o algoritmo de minimização separa mais os estados, 
e isto acontece de forma interativa.
 � Os estados X e Y são n-distinguíveis caso tenha uma cadeia s ∈ Σ* de 
comprimento n, de forma que s é aceita a partir de X, mas rejeitada a 
partir de Y, ou vice-versa.
 � O algoritmo procura uma partição, de tal forma que os estados não 
equivalentes fiquem em blocos distintos e que usem o menor número 
possível de blocos.
Por fim, o algoritmo de minimização de autômatos funciona de acordo 
com as etapas a seguir (SIPSER, 2007):
1. Produz uma partição Z0 = {F, Q – F} do conjunto de estados contidos em 
Q, separando os estados finais (F) dos não finais (Q – F).
2. Para cada bloco de estados L na partição Zi, cada símbolo s do alfabeto 
Σ, sendo cada par de estados X, Y contidos no bloco L:
a) sendo O = δ(X, s) e O’ = δ(X, s) os estados que o AFD alcança quando 
consome símbolo s a partir dos estados X, Y pertencentes ao bloco L;
b) caso O e O’ estejam contidos em blocos distintos na partição Zi, então 
os estados X e Y não possuem equivalência e devem ser separados 
na partição Zi+1.
3. Se a partição Zi+1 não for igual à partição Zi, deve-se repetir a etapa 2.
4. O autômato mínimo é formado de tal maneira que os seus estados são 
os blocos contidos da enésima partição Zi+1 gerada.
A seguir, nas Figuras 11 a 14, a execução do algoritmo de minimização de 
AFD é aplicada, sendo mostrada a redução da quantidade de estados em 
cada interação executada.
Autômatos finitos determinísticos16
Figura 11. Diagrama D1 que será minimizado. 
Figura 12. Interação 1 sobre o D1.
Figura 13. Interação 2 sobre o D1.
Autômatos finitos determinísticos 17
Figura 14. Interação 3 sobre o D1. 
Observe que o diagrama D1, que anteriormente tinha 6 estados, após 
a aplicação do algoritmo de minimização de AFD ficou com 4 estados, não 
tendo o funcionamento alterado, apenas o número de estados reduzidos.
Você sabia que o AFD utiliza operações regulares? O que é isso? São 
mecanismos usados para detectar se uma linguagem é regular ou não, 
podendo definir estratégias de como manipular uma linguagem. São definidas 
três operações sobre linguagens regulares, sendo elas:
 � união (A U B = { x | x ∈ A ou x ∈ B});
 � concatenação (A • B = { xy | x ∈ A ou y ∈ B}) 
 � estrela (A* = { x1x2...xk | k ≥ 0 e cada xi ∈ A }).
Referências
DIVERIO, T. A.; MENEZES, P. B. Teoria da computação: máquinas universais e computa-
bilidade. 3. ed. Porto Alegre: Bookman, 2011. 288 p. (Série Livros Didáticos Informática 
UFRGS, 5).HOPCROFT, J. E.; MOTWANI, R.; ULLMAN, J. D. Introdução à teoria de autômatos, 
linguagens e computação. Rio de Janeiro: Campus; Elsevier, 2003. 560 p.
LEWIS, H. R.; PAPADIMITRIOU, C. H. Elementos da teoria da computação. 2. ed. Porto 
Alegre: Bookman, 2004. 344 p.
MENEZES, P. B. Linguagens formais e autômatos. 6. ed. Porto Alegre: Bookman, 2011. 
256 p. (Série Livros Didáticos Informática UFRGS, 3).
SIPSER, M. Introdução à teoria da computação. São Paulo: Cengage Learning, 2007. 459 p.
Autômatos finitos determinísticos18
Dica do Professor
O software JFLAP apresenta muitos recursos implementados (autômato finito, máquina de Mealy e 
Moore, entre outros), entre eles a criação e as simulações de AFD, podendo realizar ainda outras 
operações com AFD. Por meio do JFLAP, é possível ver em tempo real o AFD sendo construído e 
funcionando, bem como as movimentações entre os estados a partir dos símbolos consumidos.
Na Dica do Professor, você verá a criação e a simulação de um AFD para reconhecer determinada 
linguagem, buscando, assim, a fixação do conteúdo por meio da utilização de uma interação gráfica 
ou software chamado JFLAP.
Aponte a câmera para o código e acesse o link do conteúdo ou clique no código para acessar.
https://fast.player.liquidplatform.com/pApiv2/embed/cee29914fad5b594d8f5918df1e801fd/ff2a3e2c6d268ccedb4108ffa61e79d7
Exercícios
1) Os autômatos, ou máquinas de estados, são abstrações matemáticas para representar 
modelos computacionais. Esses modelos computacionais possibilitam a idealização de 
computadores, podendo representar linguagens complexas, tais como as recursivas e 
recursivamente enumeráveis às simples linguagens regulares. Um dos tipos de autômatos 
usados para reconhecer a linguagem regular é o AFD, marcado fortemente por seu 
determinismo. 
Assinale a alternativa correta acerca do significado de determinismo usado pelo AFD.
A) É a capacidade que um autômato finito tem de chegar a dois estados diferentes por meio da 
transição espontânea épsilon, sendo essa transição determinante no estado de aceitação.
B) É a capacidade que um autômato finito com estado finito tem de assegurar que pode ou não 
utilizar um símbolo, ficando a cargo do estado não consumir todos os símbolos do alfabeto, 
sendo o consumo dos símbolos optativo.
C) É a capacidade que um autômato com estados finitos e predefinidos estabelece a partir de 
seus estados iniciais de alcançar o único estado de aceitação possível, caracterizando o 
determinismo.
D) É a capacidade que um autômato finito tem de gerar um único ramo de computação para 
cada cadeia de entrada fornecida. Esse autômato pode ser expressado por meio da quíntupla 
da formalização.
E) É a capacidade que um autômato finito tem de realizar sua computação na função programa 
por meio de três estados iniciais e dois estados de aceitação, sendo esta a quantidade mínima 
de estados apropriados. 
O diagrama de estados usado no AFD é um recurso gráfico muito expressivo para 
representar muitas máquinas, entre elas as máquinas de estados finitas. Com esse diagrama, 
é possível estabelecer a transição de um estado para outro por meio do consumo dos 
símbolos disponíveis no alfabeto em questão. A seguir, são informados detalhes sobre um 
diagrama de estados:
 
Q = {q0, q1, q2, q3, q4, q5},
Σ = {0, 1},
Função programa = {
δ(q0, 0) = q5, δ(q0, 1) = q1,
2) 
δ(q1, 0) = q2, δ(q1, 1) = q5,
δ(q2, 0) = q5, δ(q2, 1) = q3,
δ(q3, 0) = q4, δ(q3, 1) = q5,
δ(q4, 0) = q4, δ(q4, 1) = q4,
δ(q5, 0) = q0, δ(q5, 1) = q0
}
q0 é q0.
F = { q0, q4}
 
De acordo com as informações, indique qual diagrama corresponde às especificações 
descritas.
A) 
B) 
C) 
D) 
E) 
O diagrama de estados usado no AFD é um recurso gráfico muito expressivo para representar 
muitas máquinas, entre elas as máquinas de estados finitas. Com esse diagrama, é possível 
estabelecer a transição de um estado para outro por meio do consumo de todos os símbolos 
disponíveis no alfabeto usado em determinada linguagem. A seguir, é esboçado o diagrama 
2.Determine a linguagem L(M2) aceita pelo AFD M2 representado no diagrama.
3) 
 
A) L(M2) = {w ∈ (0, 1)* | w é formada por uma cadeia de comprimento ímpar e 
contendo sequencialmente 0s e 1s}.
B) L(M2) = {w ∈ (0, 1)* | w é formada por uma cadeia de comprimento ímpar, tendo 0 
no meio e terminando em 1}.
C) L(M2) = {w ∈ (0, 1)* | w é formada por um cadeia que deve ter uma sequência 
mínima de três 1s consecutivos}.
D) L(M2) = {w ∈ (0, 1)* | w é formada por uma cadeia que deve ter uma sequência 
mínima de quatro 1s consecutivos}.
E) L(M2) = {w ∈ (0, 1)* | w é formada por uma cadeia que deve ter uma sequência 
mínima de cinco 1s consecutivos}.
A formalização do autômato finito deteminístico (AFD) fornece a precisão e a notação para 
representar esse tipo de modelo computacional (AFD). No AFD, sua formalização pode ser 
expressada por meio da 5-upla (Q, Σ, δ, q0, F). A seguir, é esboçado o diagrama que reconhece a 
linguagem L(M3).
4) 
 
Leia as afirmativas a seguir a respeito dos componentes da formalização do AFD:
I. Esse AFD tem Q = {q0, q1, q2, q3, q4}, F = {q1, q3} e Σ = {p, a, i}.
II. Esse AFDtem Q = {q0, q1, q2, q3, q4}, F = {q3}, δ(q0, a) = q0.
III. Esse AFD tem Q = {q0, q1, q2, q3, q4}, F = {q3}, Σ = {p, i}, q0 = q1.
IV. Esse AFD tem Q = {q0, q1}, F = {q2} e Σ = {p, a, i}, δ(q2, a) = q2, δ(q2, p) = q2.
V. Esse AFD tem Q = {q0, q1, q2, q3, q4}, Σ = {p, a, i}, δ(q0, i) = q0.
Assinale a alternativa que contém as assertivas corretas:
A) I e IV.
B) I e V.
C) I, II e III.
D) II e III.
E) II e V.
5) 
Em AFDs, pode haver muitas soluções para o mesmo problema, incluindo aquelas soluções 
com muitos estados. Ao implementar um AFD, uma pergunta pertinente que se deve fazer é 
se o AFD foi construído com o menor número possível de estados. Com isso, é apropriada a 
utilização do algoritmo de minimização de autômatos.
Analise as afirmativas a seguir, que tratam das características do algoritmo de minimização 
de autômatos, e classifique-as em verdadeiras (V) ou falsas (F):
( ) Neste algoritmo, os estados finais e os não finais são separados na primeira interação, 
depois são unidos, chegando a ser indissolúveis.
( ) Os estados equivalentes são aqueles que, ao consumirem um símbolo, vão ter 
comportamentos de aceitação/rejeição idênticos.
( ) O algoritmo procura uma partição, de forma que os estados não equivalentes estejam no 
mesmo bloco.
( ) A minimização do autômato finito une os estados equivalentes entre si, alterando e 
aperfeiçoando o funcionamento do autômato.
Assinale a alternativa que apresenta a ordem correta:
A) F, V, F, V.
B) F, V, F, F.
C) V, F, V, V.
D) V, F, F, V.
E) F, V, V, F.
Na prática
Atualmente há muitos acidentes causados por erros em sistemas que controlam elevadores 
prediais, sendo este um problema que merece atenção por conta dos perigos envolvidos com os 
seus usuários. É comum que determinado andar de um prédio não esteja ou não seja acessível a 
partir do elevador; dessa forma, deve-se evitar que tal andar seja solicitado.
Neste Na Prática, você acompanhará um problema que ocorre em muitas situações do cotidiano 
nos sistemas que controlam elevadores, em que é proposto um autômato finito determinístico para 
modelar o problema em questão.
Aponte a câmera para o 
código e acesse o link do 
conteúdo ou clique no 
código para acessar.
https://statics-marketplace.plataforma.grupoa.education/sagah/05cbc642-ddb0-4252-a35b-ed2dfb895f18/4734ec77-d57e-4629-a240-65660d2b0d1e.jpg
Saiba mais
Para ampliar o seu conhecimento a respeito desse assunto, veja abaixo as sugestões do professor:
Autômatos finitos: um formalismo para cursos na web
No link a seguir, você verá um artigo científico que propõe a modelagem de cursos disponibilizados 
via www utilizando os autômatos finitos determinísticos com uma saída.
Aponte a câmera para o código e acesse o link do conteúdo ou clique no código para acessar.
Minimização de AFDs
No link a seguir, você verá uma videoaula sobre a minimização de autômatos finitos determinísticos.
Aponte a câmera para o código e acesse o link do conteúdo ou clique no código para acessar.
Geração automática de código a partir da manipulação de 
modelos
Aqui, você irá conferir o trabalho final de especialização que utiliza a manipulação de modelos para 
gerar automaticamente códigos. Isso é realizado na integração de uma ferramenta de modelagem 
que utiliza autômatos finitos determinísticos.
Aponte a câmera para o código e acesse o link do conteúdo ou clique no código para acessar.
https://silo.tips/download/4-automatos-finitos-um-formalismo-para-cursos-na-web
https://www.youtube.com/embed/fd6SU5K3IZo
http://repositorio.utfpr.edu.br/jspui/bitstream/1/22184/1/PB_EBD_02_2017_15.pdf