Apostila Paradigmas de Programação

Prévia do material em texto

Apostila – Paradigmas de 
Programação 
José Corrêa Viana 
 
jcorrea@unipam.edu.br 
jcorreavian@hotmail.com 
twitter.com/rhuodox 
facebook.com/ jcorreaviana 
 
 
 
 
 
 
 
 
 
 
Patos de Minas, 2014. 
O que você encontrará aqui 
O objetivo dessa apostila é auxiliar no processo de aprendizado e fixação dos 
conteúdos vistos em sala de aula. Essa apostila abordará conceitos sobre: 
 Linguagens regulares; 
 Paradigma Imperativo; 
 Paradigma Lógico Funcional; 
 Paradigma Orientado a Objeto. 
Qualquer dúvida e/ou sugestões para adicionar valor a este material, basta 
entrar em contato nos meios de comunicação disponibilizados na primeira 
página dessa apostila. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Primeiros Conceitos 
Acredito que a primeira pergunta que surge em nossa mente quando 
iniciamos um novo estudo é saber por que estamos fazendo isso correto? 
Então talvez a melhor candidata como primeira pergunta dessa disciplina 
seja: “O que é Paradigma de Programação?”. Espero ter acertado que essa 
seja sua pergunta ou que seja ao menos algo semelhante. Mas vamos 
começar por ela. 
Pois bem. Paradigma de Programação nada mais é do que a estrutura ou a 
maneira que um programa será executado. Através de um exemplo fica mais 
fácil, correto?! : 
O que diferencia as linguagens Java ou C# das linguagens COBOL ou 
Pascal partindo da visão essencial de cada uma? 
Java e C# São linguagens de programação ORIENTADAS A OBJETO, ou 
seja, o programador deve ter a capacidade de abstrair que uma linguagem 
com essa característica trabalha através da interação de objetos, correto?! 
As linguagens COBOL e Pascal são linguagens onde o programador deve 
entender que o programa será executado como uma pilha de funções 
executadas de maneira sequencial, ou seja, PROGRAMAÇÃO FUNCIONAL. 
Se fizermos uma analogia com Engenharia de Software, existem diversas 
metodologias que possuem suas particularidades correto? As metodologias 
ágeis – Scrum, XP, etc - se diferenciam das metodologias tradicionais – 
Processo Unificado, Cascata, Espiral – através de suas características e 
também devido a sua aplicabilidade em determinados problemas que devem 
ser resolvidos. Os Paradigmas de Programação possuem basicamente o 
mesmo conceito: diferentes linguagens de programação possuem diferentes 
paradigmas de programação. 
Java, C#, Pascal e COBOL são poucos exemplos de linguagens que possuem 
no mercado. Vou deixar como tarefa para você pesquisar mais alguns 
exemplos de linguagens de programação e quais seus paradigmas. Para 
iniciar suas pesquisas, lhe ajudarei com uma excelente dica! Clique aqui 
para ver qual é. . 
Vamos começar então vendo alguns conceitos de linguagens regulares e 
alguns conceitos importantes, como autômatos, expressão regular e 
gramática regular. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Autômato Finito 
Então, o que é um autômato finito? 
 
 
 
 
 
 
 
 
 
 
 
 
 
Autômatos finitos são máquinas que possuem basicamente três 
componentes e que são bem fáceis de ser lembrados: 
1. Fita: dispositivo que tem a informação que será processada; 
2. Unidade de Controle: estado corrente da máquina. Essa possui uma 
unidade de controle que acessa um estado da fita e que se movimenta 
exclusivamente para a direita; 
3. Programa ou função de transição: determina o novo estado da 
máquina através de leituras e de funções. 
 
 
 
 
Figura 2 - Exemplo de um autômato de estado finito com a fita, controle e estados 
Figura 1 – Exemplos de autômatos: Semáforo, porta eletrônica e elevador. 
Através da imagem podemos ver que o funcionamento de um autômato é 
bem simples. Basicamente ele possui um caminho a ser seguido (fita) que, de 
acordo com uma função ou leitura, ele muda seu estado e para saber qual o 
estado atual é utilizado um controle ou um indicador de qual o estado atual. 
No exemplo a cima a fita é lida pelo programa como nós lemos essa apostila, 
sempre da esquerda para a direita. 
Definindo um autômato finito, temos algumas propriedades que nos ajudam 
a entender melhor como isso funciona. Vamos ver as definições formais e 
depois veremos alguns exemplos que podem nos auxiliar a compreender 
melhor os autômatos finitos. 
Autômato Finito Determinístico 
Existem algumas propriedades que são utilizadas ao realizar a diagramação 
de um autômato (veremos alguns exemplos mais à frente). 
 
Figura 3 - Representação da mudança de estados de um autômato através da leitura de um símbolo 
 
Figura 4 - Representação de um estado inicial e um estado final 
 
O que define o autômato finito é uma quíntupla (ou 5-upla) definida por: 
 , onde: 
 
 
 
 
 
Essa quíntupla pode parecer um pouco confusa no início do conteúdo, mas 
com exemplos ficará mais fácil de entender e com o passar do tempo você irá 
decorá-la intuitivamente. Prometo! . 
Vamos voltar às figuras apresentadas acima e vamos explicar como funciona 
a porta eletrônica. Essa porta é utilizada em shoppings, supermercados e em 
outros lugares. Para que ela abra automaticamente existem dois tapetes, 
um de frente para a porta do lado interno e outro tapete do lado externo. 
Isso porque pessoas devem entrar e pessoas querem sair. A porta irá abrir 
quando uma pessoa se aproximar e se fechará quando a pessoa se distanciar 
da porta. 
 
Figura 5 - Visão por cima de uma porta automática 
 
A porta pode assumir dois estados: aberto ou fechado. Ele irá mudar de um 
estado para o outro de acordo com o estímulo que receber e, nesse caso, 
existem quatro possibilidades: 
1. Frente: pessoa está no tapete da frente (me deixe entrar!); 
2. Retaguarda: pessoa está no tapete de dentro (me deixe sair!); 
3. Ambos: existe uma pessoa no tapete da frente e outra no tapete de 
dentro; 
4. Nenhum: não há ninguém sobre os tapetes. 
Vamos supor que a porta receberá a seguinte sequência de estímulos ou 
valores de entrada: 
frente; retaguarda; nenhum; frente, ambos. 
Sabemos que nesse caso a porta estará aberta ou fechada e, de acordo com a 
sequência de estímulos ela passará de um estado para outro ou ainda 
continuará no mesmo estado. Portanto, para a sequência de estímulos 
teremos as seguintes transações de estados: 
fechado (início) -> aberto; aberto -> aberto; aberto -> fechado; fechado -> 
aberto; aberto -> aberto. 
Se transpusermos todas essas frases acima em uma imagem ficam mais 
fáceis? Vamos representar em uma imagem, também chamado de diagrama 
de transições ou diagrama de estados. 
 
Figura 6 - Diagrama de transições da porta automática 
 
Ao realizar a leitura da imagem – para ajudar a esclarecer os conceitos – é 
possível notar os estados e quais as leituras ou transações são realizadas 
para passagem de uma situação para outra. Vamos ler a imagem: 
 Se ninguém quer entrar ou sair, a porta permanecerá fechada; 
 Se houver alguém na frente, na retaguarda ou em ambos e a porta 
estiver fechada, ela mudará para o estado aberta; 
 Se ainda existir pessoas na porta da frente, na retaguarda ou em 
ambos, a porta continuará aberta; 
 Se a porta estiver aberta, porém mais ninguém irá passar, ela 
mudará do estado aberta para fechada. 
Esse é um exemplo inicial. Daqui a pouco iremos utilizar programasque 
simulam o funcionamento de autômatos e poderemos ver de uma maneira 
mais interativa como eles funcionam. 
Para exercitar a transição entre os estados do autômato, teste e nesse 
momento, tente entender como é a feita a passagem de estados no autômato. 
CLIQUE AQUI E FAÇA ALGUNS TESTES! 
“Se estiver com alguma dúvida, clique no ícone “?” que o site irá compilar 
passo a passo a transição dos estados do autômato. 
Representação de um Autômato Finito 
Iremos ver nessa apostila basicamente três tipos de representações de 
autômatos finitos: 
1. Definição formal ou linguagem formal; 
2. Através do diagrama de transições; 
3. Através da tabela de transições. 
Agora vamos ver um exemplo que apresenta as três maneiras dessa 
representação: 
Especifique formalmente um autômato finito determinístico (DFA) que 
aceite somente strings de a’s e b’s que têm a sequência ab em algum lugar 
da string. 
 
Portanto, podemos definir de maneira formal essa linguagem L como: 
{ | Z e X que consistem somente em 
a’s e b’s 
Ou ainda podemos definir apresentado os parâmetros a e b à esquerda da 
barra vertical: 
{ | 
Exemplos de strings nessa linguagem: ab; bbaba; baaaabb, aaaaaaaaab. 
Exemplos de strings que não estão nessa linguagem: a; bbbaaa; ba. 
Podemos deduzir que: 
 O alfabeto de entrada será ∑ = {a, b}; 
 Possui um conjunto de estados, onde vamos dizer que q0 é o estado 
inicial; 
 O autômato deve armazenar algumas informações para que a string 
passada seja uma substring de entrada: 
1. Já viu ab? Então vai aceitar todas as demais entradas e só 
estará em estado de aceitação; 
2. Nunca viu ab, mas sua entrada mais recente foi a? Então se ele 
ver um b, terá visto ab e poderá aceitar o que vier em diante; 
3. Nunca viu ab, mas sua entrada ou não existe ou começa com a? 
Então ele não poderá aceitar até ver o primeiro a seguido de b. 
Agora vamos atribuir para cada situação dessa um estado. 
 Estado 3: será representado pelo estado q0. Precisamos ver uma 
sequência ab. Porém, se no estado q0 vermos b, então devemos ficar 
no estado q0. 
o δ (q0, b) = q0; 
 Estado 2: estamos no estado q0 e vemos um a, mas nunca vimos um 
ab. Esse estado será o q2. Portanto se a entrada for a, então podemos 
passar para o estado 2. 
o δ (q0, a) = q2; 
 Estado 3: nesse estado será considerado que estamos no estado 2. 
Então, se virmos outra letra a estaremos no mesmo lugar correto? 
Ainda não vimos uma sequência ab ! Não vimos ab, mas a ainda 
continua sendo nosso último símbolo e ainda estamos esperando pela 
letra b. 
o δ (q2, a) = q2;. 
Se estamos no estado q2 e vemos a letra b, agora existe uma 
sequência ab. Chamaremos essa condição de q1, e ela será nossa 
condição de aceitação. 
o δ (q2, b) = q1; 
Como foi definido no problema, ao final dessa condição, se vermos uma 
sequência ab, qualquer entrada será aceita e continuará na situação de 
aceitação. 
o δ (q1, a) = δ (q1, b) = q1; 
Agora podemos definir nosso autômato aplicando a quíntupla vista 
anteriormente. Q = {q0, q1, q2}. Como foi definido, q0 será o estado inicial e 
o único estado de aceitação é q1, ou seja, F = {q1}. A definição completa do 
autômato A que aceita a linguagem L de strings que tem como subconjunto 
ab, é: 
 { { { 
Já vimos uma definição formal do autômato. Essa representação é a mais 
extensa e pode ficar até um pouco cansativa de se visualizar um autômato. 
Vamos ver agora duas outras formas de representação. 
A representação por diagrama já foi vista anteriormente no exemplo da 
porta automática, lembra-se? Vamos ver algumas definições para esse tipo 
de representação: 
 Para cada estado Q existe um nó correspondente; 
 Cada para cada mudança de estado existirá um estado resultante. Essa 
mudança se deve com a entrada do estado atual e da função de 
transição. δ (q, a) = p. Ou seja, o estado q após passar pela função de 
transição a resultará em p; 
 Existe uma seta inicial em q0 identificada como início. Essa seta não se 
origina em nenhum estado (representados por nós); 
 Os estados ou nós de aceitação são representados por um círculo duplo 
e os estados que não estão nessa situação são círculos simples. 
 
Figura 7 - Diagrama de transições que aceita todas strings que contêm a substring ab 
 
A última representação que iremos ver é a tabela de transições. Essa 
representação e através (como o nome já diz né, hehe) através de uma tabela 
que representa como se devem as mudanças de um estado para outro. As 
linhas correspondem aos estados, e as colunas correspondem às entradas. 
A tabela de transição que representa o exemplo que estamos acompanhando 
é dada por: 
 a b 
→ q0 q2 q0 
* q1 q1 q1 
q2 q2 q1 
 
Tabela 1 - Tabela de transição do exemplo anterior 
 
Nesse caso, o estado inicial é representado com uma seta, e os estados de 
aceitação são marcados com um asterisco. 
 
Função de Transição Estendida 
Essa é outra maneira de representar os autômatos. Através da fórmula de 
transição de estados é possível responder se uma palavra pode ou não ser 
aceita por um autômato. Vamos ver como essa representação funciona 
através de duas palavras para o autômato anterior. 
1. baabaab 
Através da função estendida, temos: 
δ (q0, baabaab) 
δ (q0, b) aabaab = q2 
δ (q2, a) abaab = q2 
δ (q2, a) baab = q2 
δ (q2, b) aab = q1 
δ (q2, a) ab = q1 
δ (q2, a) b = q1 
δ (q2, b) ε = q1 -> PALAVRA ACEITA 
2. baa 
δ (q0, baa) 
δ (q0, b) aa = q0 
δ (q0, a) a = q2 
δ (q0, a) ε = q2 -> PALAVRA REJEITADA 
Note que as expressões seguem a tabela de transição ou o diagrama do 
autômato. O símbolo ε indica que não existem mais entradas para serem 
lidas, portanto ao ver essa letra, o autômato irá ler o último valor e o estado 
de saída será o estado final da palavra. Caso esse estado seja de aceitação a 
palavra será aceita, do contrário será rejeitada. 
Autômato Finito Não Determinístico 
Bem, até agora trabalhamos com Autômatos Finitos Determinísticos, ou 
seja, são autômatos que partem de um estado e vão para outro estado. Pois 
bem, existem ainda outras formas de representação que são utilizadas para 
facilitar a representação de fórmulas matemáticas: são os Autômatos Finitos 
Não Determinísticos. 
A diferença entre um determinístico – AFD – e um não determinístico – 
AFN – são os estados. Em um AFD temos um estado determinado, onde 
através da função de transição passamos do estado q0 para q1 por exemplo. 
No caso do AFN podemos ter um conjunto de estados, ou seja, de q0 é 
possível ir para q1 ou q2. Vamos ver essa representação de autômato em um 
diagrama. 
 
Figura 8 - Representação de um Autômato Finito Não Determinístico 
O interessante nesse autômato é que podemos através de uma mesma 
entrada estar em dois estados ao mesmo tempo. Por isso o nome não 
determinístico. Não é possível garantir que um autômato terá apenas um 
estado resultante, mas agora ele poderá ter um conjunto de estados 
resultantes. Interessante, não? A ideia dos autômatos finitos não 
determinísticos é simplificar a representação dos autômatos finitos. 
Portanto, por analogia podemos presumir que para cada autômato finito não 
determinístico teremos um autômato finito determinístico. 
CLIQUE AQUI PARA SABER MAIS SOBRE A HISÓRIA DOS AFN 
Nosso foco no curso será ver como podemos converter um AFN para um AFD 
(vamos tentar usar as siglas para simplificar agora, ok?!). Assim, caso tenha 
mais interesse sobre os AFN’s, utilize a internet para aprimorar seus 
conhecimentos sobre esse assunto. Essaapostila é apenas um direcionador 
para seus estudos. Você e somente você pode definir se você quer aprender 
mais ou não, jovem pandawan ! 
O que define o AFN é uma quíntupla (ou 5-upla) definida por: 
 , onde: 
 
 
 
 
 
 
Se compararmos com o AFD, a diferença da 5-upla é a função de transição. 
Nesse caso ela indica que após passarmos por uma função de transição 
poderemos ter como resultado um conjunto de estados ou partes de Q 
(podemos ter mais de um estado). 
Em um AFN teremos estados que estarão inacessíveis e que, portanto, 
podem ser descartados para simplificar o nosso autômato. No pior dos casos, 
ao converter um AFN para um AFD podemos ter novos estados. Isso nem 
sempre irá acontecer devido à remoção dos estados inacessíveis a partir do 
estado inicial. 
Converter AFN em AFD 
 
Para realizar a conversão de um AFN para AFD iremos nos concentrar 
basicamente na tabela de transição e no diagrama de representação do 
autômato. Estendendo a fórmula de transição também é possível provar essa 
conversão, mas esse não será nosso foco. Deixo aqui um site que apresenta a 
transição de um AFN para AFD estendendo a fórmula de transição. 
Pois bem, mãos a obra! 
Sabemos que através de um diagrama de representação do autômato 
podemos elaborar nossa tabela de transição. Então vamos utilizar o 
autômato apresentado no tópico anterior. 
A partir de agora iremos construir o autômato finito através da tabela de 
transição. Para isso, iremos considerar as linhas em nossa tabela onde os 
estados que possuem um estado de acesso. Como estado de acesso podemos 
considerar como todos os conjuntos de onde existe o estado inicial. Isso 
porque não conseguimos aceitar ou rejeitar uma palavra, desde que ela não 
passe pelo estado inicial. Vou provar isso através de um exemplo por 
indução!  
Para o autômato acima, queremos ver se a entrada 00101 será aceita. 
No exemplo, temos que caso a entrada seja 0, o autômato pode continuar no 
estado q0 ou ir para o estado q1 correto? Vamos fazer a prova aos poucos. 
 0 
q0 q0 
 q1 
Ok. Até aqui estamos em dois estados, ou q0 ou q1 serão aceitos. Isso será 
válido pois o primeiro valor da entrada foi 0. Agora o autômato receberá 
outro 0. Agora ele seguirá somente por q0 novamente. O estado q1 será 
parado pois caso q1 receba zero ele não irá para nenhum lugar, ou seja, 
ficará paralisado. Indicarei paralisado com o símbolo P. 
 0 0 
q0 q0 q0 
 q1 (P) q1 
Já sabemos que q0 aceita como próximos estados q0 e q1. Portanto eles se 
repetem. O próximo valor de entrada será 1. Agora devemos considerar o 
seguinte: caso q0 receba o valor 1, ele continuará em q0 e caso q1 receba o 
valor 1 o autômato irá para q2. 
 0 0 1 
q0 q0 q0 q0 
 q1 (P) q1 
 q2 
Chegamos ao estado final, porém nossa palavra ainda não acabou. 
Precisamos continuar para finalizar todos os valores da palavra. A próxima 
entrada será 0. Então agora q2 será paralisado, pois não tem para onde ir e 
no caso de q0 ele novamente terá duas opções. Ou continua no estado q0 ou 
vai para o estado q1. 
 
 0 0 1 0 
q0 q0 q0 q0 q0 
 q1 (P) q1 q1 
 q2 (P) 
Nossa última entrada será 1. Portanto, q0 continuará em q0 mas q1 irá para 
q2. Como existe um conjunto e estados {q0, q1} ao final da palavra, ela será 
aceita pois q2 é um estado de aceitação. 
Consideramos que uma palavra seja aceita caso ela termine em qualquer 
conjunto de estados que possua um estado final ou de aceitação. 
 0 0 1 0 1 
q0 q0 q0 q0 q0 q0 
 q1 (P) q1 q1 
 q2 (P) q2 
Portanto, podemos ver que para que uma palavra seja aceita ela deve 
sempre passar pelo estado inicial – nesse caso, q0 – pois para transitar entre 
os demais estados os valores que ainda devem ser lidos partem do início do 
autômato. Assim, os estados válidos e utilizados para transformar um AFN 
em AFD são somente aqueles conjuntos de estados que possuem o estado 
inicial. Os demais estados são denominados inacessíveis. Isso porque não é 
possível chegar até ele sem que passemos pelo estado inicial. 
Agora é hora de fazer algumas alterações na tabela de transição para 
conseguirmos fazer nosso AFN se transformar em AFD. Para facilitar a 
leitura dos estamos podemos criar apelidos para as linhas de transição. Isso 
não é obrigatório ok?! É só para a tabela ficar mais apresentável e fácil de 
entender. Serão criadas mais duas colunas. Uma coluna para sabermos 
quais estados estão acessíveis e que devemos utilizar para criar o AFD. A 
coluna Acessível terá o valor “S” para sim e “N” para não. A outra coluna 
será o apelido para cada coluna. Ao invés de representarmos por conjuntos 
de estados representaremos por letras do alfabeto. 
Apelido Acessível? 0 1 
A N Ø Ø Ø 
B S → q0 q0, q1 q0 
C N q1 Ø q2 
D N *q2 Ø Ø 
E S q0, q1 q0, q1 q0, q2 
F S *q0, q2 Ø q2 
 
Tabela 2 - Construindo os subconjuntos do AFN para transformá-lo e AFD 
Podemos ver através da tabela acima que os estado acessíveis serão três. B, 
E, F. Isso porque eles possuem com característica comum o estado inicial, e 
por isso são estados acessíveis. Vamos agora renomear os estados para ver 
como a tabela fica. 
Apelido Acessível? 0 1 
A N A A A 
B S -> B E B 
C N C A D 
D N D A A 
E S E E F 
F S F E B 
 
Tabela 3 - Renomeando os estados do autômato 
Vamos considerar agora apenas os estados acessíveis para fazermos nosso 
AFD. 
Apelido Acessível? 0 1 
B S -> B E B 
E S E E F 
F S F E B 
 
Tabela 4 - Estados de aceitação do autômato 
Invertendo os apelidos para as funções temos. 
Apelido Acessível? 0 1 
B S → q0 q0, q1 q0 
E S q0, q1 q0, q1 q0, q2 
F S *q0, q2 Ø q2 
 
Tabela 5 - Estados de aceitação do autômato 
Agora podemos representar do AFD do AFN apresentado. Com ele podemos 
confirmar que para o AFN realmente existe seu respectivo AFD. 
 
Figura 9 - AFD convertido através do AFN 
 
É possível aplicar qualquer palavra para testar o autômato. Faça um teste 
com a palavra utilizada no exemplo anterior para provar a regra do AFN e 
veja se ela será aceita ou rejeitada. Você verá que o resultado será o mesmo 
do apresentado na explicação. Quando temos uma transição para um 
conjunto de estados, qualquer conjunto que tenha o estado final será um 
estado de aceitação. Como dito no início dos AFN, eles são utilizados para 
simplificar a representação dos AFD. 
 
Autômatos de Conexão 
 
Olá! Estamos quase finalizando nosso assunto sobre autômatos. A proposta 
de estudos apresentados aqui aborda de maneira limitada informações sobre 
isso. Portanto, caso tenha interesse, não deixe de correr atrás de materiais e 
assuntos relacionados. 
Os autômatos de conexão são aplicados para realizar a eliminação de 
estados não acessíveis no conjunto de possíveis estados do autômato. Ela se 
baseia na área de minimização de autômatos, que será nosso próximo e 
último capítulo sobre isso. 
O autômato de conexão se baseia na variação da equação utilizada pela 
definição de autômato. A função do autômato é: 
 
Nos autômatosde conexão é necessário identificar quais são os estados não 
acessíveis e esses serão agrupados em um conjunto. Baseado nisso é possível 
derivar a função para os autômatos de conexão: 
 , onde 
 
 
 
 
 
 
 
Podemos identificar quais são os autômatos não acessíveis apenas lendo o 
diagrama de autômato. Para realizarmos a prova desses autômatos será 
utilizada uma árvore para provar quais estados são acessíveis e quais não 
são. Existem algumas regras que devem ser seguidas para 
elaboração/apresentação da árvore: 
1. A raiz da árvore é o estado inicial (q0); 
2. Os filhos do nó q0 são todos os estados que se relacionam com o 
mesmo através da transição de estados; 
3. Devem-se explorar os nós filhos da mesma forma que q0; 
4. Se algum estado já foi explorado anteriormente, não é necessário 
explorá-lo de novo; 
5. Parar quando todos os nós foram explorados. 
 
Figura 10 - Exemplo de autômato para aplicação das regras do Autômato de Conexão 
 
Através da Figura 10 é possível visualizar que os estados G e H não são 
alcançados por nenhum estado. Existem transições a partir deles, mas não 
existem transições de outros estados para eles. Os estados G e H são 
exemplos de estados não acessíveis. 
Vamos realizar a prova de que esses estados não são acessíveis através da 
montagem da árvore de estados. 
 
Figura 11 - Árvove para identificação de Autômato de Conexão 
 
Após a eliminação dos estados não acessíveis, baseado na árvore, teremos 
como resultado o seguinte Autômato de Conexão: 
 
Figura 12 - Autômato de Conexão gerado 
 
Minimização de Autômatos 
 
Chegamos ao nosso último capítulo sobre autômatos. Esse último tópico 
falará sobre minimização de autômatos finitos. A proposta da minimização é 
A 
B 
E 
D 
F 
D E 
E 
F 
F 
C 
A A 
obter o menor autômato possível e que não afete o comportamento do 
autômato. Fazendo um apanhado geral, iremos unir a ideia da conversão de 
AFN em AFD e também a seção sobre Autômatos de Conexão. 
Sem mais delongas, vamos ao que interessa!  
Vamos seguir algumas regras para realizar a minimização do autômato: 
1. Identificar o autômato de conexão. Isso é necessário para remover 
todos os estados que não são acessíveis a partir do estado inicial; 
2. Elabore a tabela de transição de estados, classificando em estados 
distinguíveis ou estados equivalentes: 
 Estados equivalentes é um conjunto de estados C {A, B} onde a 
partir da mesma entrada ambos terminam obrigatoriamente 
em estados iniciais ou estados finais: 
δ (A, 0) = C (onde C pertence ao conjunto dos estados finais); 
δ (B, 0) = C (onde C pertence ao conjunto dos estados finais); 
 Estados distinguíveis é um conjunto de estados qualquer C {A, 
B} onde a partir da mesma entrada, um dos estados irá para o 
estado inicial e o outro irá para um estado final. 
δ (A, 0) = C (onde C pertence ao conjunto dos estados finais); 
δ (B, 0) = D (onde D não pertence ao conjunto dos estados finais); 
 Para auxiliar nessa construção é importante elaborar a Tabela 
de Não-Equivalência dos estados. 
3. Construa o DFA com número mínimo de estados equivalente ao 
autômato original, considerando a tabela de transição e a 
equivalência de conjunto de estados. 
Como exemplo, iremos realizara minimização do Autômato de Conexão 
gerado na seção anterior. 
 
Figura 13 - Autômato para ser minimizado 
 
Para iniciar, devemos obedecer dois pré-requisitos: 
1. O autômato deve ser um AFD. 
 Caso não seja é necessário realizara a conversão de AFN para 
AND; 
2. É necessário remover todos os estados não acessíveis a partir do 
estado inicial. 
 Aplicação da identificação dos Autômatos de Conexão. 
Nesse exemplo, todos os dois requisitos já são obedecidos. Portanto podemos 
pular o passo 1 do processo de minimização. Vamos então para a tabela de 
não-equivalência de estados. Essa tabela é uma matriz que deve comparar 
todos os possíveis conjuntos de estados. Podemos ver que os conjuntos são os 
pares de estados onde um estado deve se diferir do outro, ou seja, 
desconsideramos o conjuntos {A, A}, {B, B}. {C, C}, {E, E}, {F, F}. 
Para aplicar o preenchimento da tabela, seguiremos a seguinte regra: 
 Se um conjunto de estados for distinguível iremos marcar com um ‘X’; 
 Se um conjunto de estados for equivalente iremos marcar com um ‘O’; 
Para iniciar o preenchimento, podemos aplicara regra do conjunto vazio. 
Essa regra diz que caso seja possível provar que um estado de um conjunto, 
quando recebe uma string vazia é diferente do outro estado, ele será 
distinguível. Isso será bem claro ao compararmos um estado final com um 
não final. Aplicando a regra, temos, por exemplo: 
 = NÃO FINAL; 
δ (F = FINAL; 
Portanto esse é um conjunto de estados distintos ou distinguíveis. 
Podemos fazer isso para todos os estados com conjuntos vazios onde F ou E 
são comparados, com exceção do conjunto {E, F}, pois ambos são estados 
finais e, portanto, são equivalentes (inicialmente). 
→A 
B 
C 
D 
*E X X X X 
*F X X X X 
 →A B C D *E *F 
Tabela 6 - Tabela de Estados Não-Distinguíveis 
Para os demais estados devemos realizar a o testes com strings para 
identificar se os demais conjuntos são acessíveis ou não. Como com o 
conjunto de estados vazios não ajuda nesse preenchimento, devemos passar 
strings para os conjuntos de estados para testar a equivalência. Vamos 
analisar o conjunto {A, D}, para a string 0. 
δ (A, 0) = B = NÃO FINAL; 
δ (D, 0) = F = FINAL; 
Portanto esse também é um conjunto de estados distintos ou distinguíveis. 
Caso com o valor 0 eles se mantivessem equivalentes, seria necessário testar 
com outro conjunto de strings para testar sua equivalência. Vamos ver outro 
exemplo para o conjunto {A, C}. 
 
δ (A, 0) = B = NÃO FINAL; 
δ (C, 0) = A = NÃO FINAL; 
Não deu certo com 0 . Vamos tentar com 1; 
δ (A, 1) = C = NÃO FINAL; 
δ (C, 1) = A = NÃO FINAL; 
Não deu certo com 1 . Vamos tentar com 01; 
δ (A, 01) = F = FINAL; 
δ (C, 01) = C = NÃO FINAL; 
Deu certo com 01 . Aplicando a string 01 para A e para C, provamos que 
eles são distinguíveis. Preenchendo o restante da tebela, teremos a seguinte 
situação: 
→A 
B X 
C X X 
D X O X 
*E X X X X 
*F X X X X O 
 →A B C D *E *F 
Tabela 7 - Tabela de Estados Não-Equivalentes preenchida 
Estamos com dois conjuntos com algumas particularidades: {D, B} e {E, F} 
são estados equivalentes. Isso porque qualquer string que passarmos para 
esses conjuntos eles terminarão no mesmo grupo. Vou deixar essa etapa 
para você. Teste algumas entradas e verifique a saída de cada um. Não se 
esqueça da regra de que a string aplicada para um deve ser a mesma para o 
outro, senão não vale ! 
Agora temos que aplicar nossa última regra que é a equivalência de conjunto 
de estados. Aqui vão algumas dicas: 
 Todos os estados que são equivalentes (possuem o ‘O’) estarão em 
nosso conjunto; 
 Todos o que a interseção entre o mesmo conjunto tenha apenas 
estados distinguíveis também estará (Não possuem ‘O’); 
Portanto, nosso conjunto de estados distinguíveis será: 
C = { {A}, {C}, {B, D}, {E, F} }; 
Agora podemos montar o Autômato Mínimo aplicado a transição entre os 
estados nos baseando no autômato original. 
 
Figura 14- Autômato Minimizado 
Algumas outras informações importantes: 
 O conjunto que tenha o estado inicial será o nosso estado inicial; 
 Todoo conjunto que possua o estado final (não obrigatoriamente 
todos) será nosso estado final; 
 Qualquer transição realizada com esse autômato será semelhante ao 
autômato anterior.