Aula 3 - Linguagens Regulares.pdf

Prévia do material em texto

Linguagens Regulares
Linguagens Formais
Introdução
 A teoria mostra que há quatro classes de gramáticas capazes 
de gerar quatro classes correspondentes de linguagens, de 
acordo com a denominada Hierarquia de Chomsky
 Hierarquia de Chomsky
 Classificação de gramáticas formais descrita em 1959 pelo 
linguista Noam Chomsky
 Possui 4 níveis
 Os dois últimos níveis (os níveis 2 e 3) são amplamente 
utilizados na descrição de linguagem de programação e na 
implementação de interpretadores e compiladores
 O nível 2 é utilizado em análise sintática (computação) e o nível 
3 em análise léxica
José Couto Júnior - jose.junior@pro.unifacs.br2
Introdução
 Hierarquia de Chomsky
José Couto Júnior - jose.junior@pro.unifacs.br3
Hierarquia de Chomsky
Gram. com estrutura de frase - Tipo 0
José Couto Júnior - jose.junior@pro.unifacs.br4
 As linguagens geradas por estas gramáticas são chamadas de 
Linguagens com Estrutura de Frase (LEF) ou Linguagens 
Recursivamente Enumeráveis ou Linguagens do Tipo 0.
 Nenhuma limitação é imposta. São capazes de 
reconhecer linguagens recursivamente enumeráveis.
 Reconhecedores: Máquinas de Turing
 é um modelo abstrato de um computador, que se restringe 
apenas aos aspectos lógicos do seu funcionamento (memória, 
estados e transições) e não à sua implementação física
Hierarquia de Chomsky
Gram. com estrutura de frase - Tipo 0
José Couto Júnior - jose.junior@pro.unifacs.br5
L = { anbncn | n > 0}
abc, aabbcc, aaabbbccc
G = (V,T,P,S)
Regras de Produção:
u w
Sendo que u  (T V)+ e w  (T V)*
Exemplos:
A  aAb
B  Ɛ
bAc aA
Hierarquia de Chomsky
Gram. com estrutura de frase - Tipo 0
José Couto Júnior - jose.junior@pro.unifacs.br6
L = { anbncn | n > 0}
Máquina de Turing
Hierarquia de Chomsky
Gram. sensíveis ao contexto - Tipo 1
José Couto Júnior - jose.junior@pro.unifacs.br7
 Gramática formal em que os lados esquerdo e direito de 
qualquer regra de produção podem ser cercados por um 
contexto de símbolo terminal e símbolo não-terminal. São 
mais gerais do que as gramáticas livres de contexto (Tipo 2).
 Para as GSC, as produções são todas da forma  b, com 
|| < |b| (produções não decrescentes) onde , b  (Vn
Vt)+
 nenhuma substituição pode reduzir o comprimento 
da forma sentencial à qual a substituição é aplicada
LEMBRETE
Vn = conjunto de não terminais
Vt = conjunto de terminais
(Vn Vt)+ = terminais unidos a não terminais, exceto Ɛ
|| = comprimento de 
Hierarquia de Chomsky
Gram. sensíveis ao contexto - Tipo 1
José Couto Júnior - jose.junior@pro.unifacs.br8
 As linguagens geradas por esta gramática são chamadas de 
Linguagens Sensíveis ao Contexto (LSC) ou Linguagens 
do Tipo 1.
 Toda gramática do tipo 1 é também do tipo 0
 Reconhecedores: Máquina de Turing com memória limitada
G2 = ({S,C}, {a,b,c},P2,S) 
P2 = { S  abc 
ab aabbC
Cb  bC
Cc  cc }
Hierarquia de Chomsky
Gram. sensíveis ao contexto - Tipo 1
José Couto Júnior - jose.junior@pro.unifacs.br9
 Linguagens Sensíveis ao Contexto
L = { anbncn | n > 1} abc, aabbcc, aaabbbccc
G = (V,T,P,S)
Regras de Produção:
u w
Sendo que u  (T V)+ e w  (T V)* e |u| < |v|
Exemplos:
A  aAb
Cc aAc
Aa  bB
B  b
Hierarquia de Chomsky
Gram. Livres de Contexto ou Tipo 2
José Couto Júnior - jose.junior@pro.unifacs.br10
 São aquelas em que é levantado o condicionamento das 
substituições impostas pelas regras definidas pelas produções
 São aquelas cujas regras de produção são da forma, ou seja, 
quando do lado esquerdo da regra há apenas um 
símbolo não-terminal (uma variável) : 
A   onde A Vn,  V+
G = (Vn, Vt, P, S)
G = ({S,A,B}, {a,b}, P,S)
P = {S  aB | bA
A  a | aS | bAA
B  b | bS | aBB }
Hierarquia de Chomsky
Gram. Livres de Contexto ou Tipo 2
José Couto Júnior - jose.junior@pro.unifacs.br11
 As linguagens geradas pelas Gramáticas Livres de Contexto 
ou do Tipo 2 são chamadas de Linguagens Livres de 
Contexto (LLC) ou Linguagens do Tipo 2. 
 Reconhecedores: autômatos com pilha
 Toda gramática do tipo 2 é também do tipo 1.
Hierarquia de Chomsky
Gram. Livres de Contexto ou Tipo 2
José Couto Júnior - jose.junior@pro.unifacs.br12
 Linguagens Livres de Contexto
L = { anbn | n > 0}
ab, aabb, aaabbb ... 
L = expressões aritméticas (+, * , [, ] )
x + x, x * x + x , x * [ x + x ] ...
L = { anbn | n > 0} S  aSb | Ɛ
G = ({S},{a,b}, P, S)
E  E + E | E * E | [E] | x
G = ({E},{+, *, [, ], x}, P, E)
Hierarquia de Chomsky
Gram. Livres de Contexto ou Tipo 2
José Couto Júnior - jose.junior@pro.unifacs.br13
 Autômato com pilha
L = { anbn | n > 0} 
Hierarquia de Chomsky
Gramáticas regulares ou Tipo 3
José Couto Júnior - jose.junior@pro.unifacs.br14
 Aplicando-se mais uma restrição sobre a forma das 
produções, pode-se criar uma nova classe de gramáticas, as 
Gramáticas Regulares (GR), de grande importância no 
estudo dos compiladores por possuírem propriedades 
adequadas para a obtenção de reconhecedores simples
 É uma restrição sobre a forma das produções
 Nas GRs, as produções são restritas às formas seguintes: 
A  aB | a (linear à direita) OU 
A  Ba | a (linear à esquerda) 
onde A,B Vn e a Vt
Hierarquia de Chomsky
Gramáticas regulares ou Tipo 3
José Couto Júnior - jose.junior@pro.unifacs.br15
 As linguagens geradas por esta gramática são chamadas de 
Linguagens Regulares (LR) ou Linguagens do Tipo 3.
 Reconhecedores: autômatos finitos
 Toda gramática do tipo 3 é também do tipo 2
 Toda LR é também uma LLC (mas nem toda LLC é LR).
G = ({S}, {a, b}, P, S) 
P = { S  aS
S  b }
L(G) = {anb| n ≥0} 
Hierarquia de Chomsky
Gramáticas regulares ou Tipo 3
José Couto Júnior - jose.junior@pro.unifacs.br16
 Linguagens regulares
L = {a(ba)*} a, aba, ababa, abababa ...
L = {(a + b)* (aa + bb)} aa, bb, aaa, aaabb ...
Hierarquia de Chomsky
Gramáticas regulares ou Tipo 3
José Couto Júnior - jose.junior@pro.unifacs.br17
 Gramáticas regulares
L = {a(ba)*} S  aA
AbaA | Ɛ
G = ({S,A},{a,b}, P, S).
L = {(a + b)* (aa + bb)} S Aaa | Abb
A Aa | Ab | Ɛ
G = ({S,A}, {a,b}, P, S) 
Hierarquia de Chomsky
Gramáticas regulares ou Tipo 3
José Couto Júnior - jose.junior@pro.unifacs.br18
 Autômato finito
L = {a(ba)*}
L = {(a + b)* (aa + bb)}
Gramáticas e reconhecedores 
José Couto Júnior - jose.junior@pro.unifacs.br19
Linguagem Gramáticas Reconhecedores 
[0] Com Estrutura de 
Frase ou 
Recursivamente
Enumeráveis
Irrestritas Máquina de Turing
[1] Sensíveis ao contexto Sensível ao contexto Máquina de Turing com 
memória limitada
[2] Livres de contexto Livre de contexto Autômato a pilha
[3] Regulares Regular Autômato finito
Hierarquia de Chomsky
Gramáticas
José Couto Júnior - jose.junior@pro.unifacs.br20
aCc aA
Cc aAc
Aa  bB
A  aAb
B aaA
A  abB
A Bab
AƐ
0
Cc aAc
Aa  bB
A  aAb
B aaA
A  abB
A Bab
AƐ
1
A  aAb
B aaA
A  abB
A Bab
AƐ
2
A  abB
A Bab
AƐ
3
Linguagens Regulares ou tipo 3
José Couto Júnior - jose.junior@pro.unifacs.br21
Linguagens Formais
Linguagens Regulares ou tipo 3
José Couto Júnior - jose.junior@pro.unifacs.br22
 Formalismos:
 Autômato finito  Formalismo operacional ou reconhecedor. 
Sistema de estados finito
 Expressão regular Formalismo denotacional. Definido a partir de 
conjuntos básicos e operações de união e concatenação
 Gramática regular  Formalismos axiomático ou gerador, mas com 
restrições da forma das regras de produção
 Linguagens mais simples
 Possível desenvolver algoritmos de reconhecimento,geração ou 
conversão entre formalismos
 Pouca complexidade
 Grande eficiência
 Fácil implementação
Linguagens Regulares ou tipo 3
José Couto Júnior - jose.junior@pro.unifacs.br23
 Possuem limitações de expressividade
 Ex: Linguagens que possuam duplo balanceamento não são 
regulares  Garantir que para cada parêntese aberto haja um 
fechado
 A maioria das linguagens de programação são NÃO regulares
 Utilizadas para realização da análise léxica
Uma linguagem é dita ser uma linguagem regular se existe 
um autômato finito que a reconhece.
José Couto Júnior - jose.junior@pro.unifacs.br24
Mas... O que é 
um autômato 
finito?
Sistema de estados finitos
José Couto Júnior - jose.junior@pro.unifacs.br25
 Modelo matemático com entradas e saídas discretas (não 
contínuo)
 Pode assumir número finito e predefinido de estados
 Cada estado resume as informações do passado para 
determinar as ações para a próxima entrada
Sistema de estados finitos - Elevador
José Couto Júnior - jose.junior@pro.unifacs.br26
Autômato Finito
José Couto Júnior - jose.junior@pro.unifacs.br27
 Sistema de estados finitos
 Constitui modelo computacional sequencial
 Utilizando em
 Linguagens formais
 Compiladores
 Semântica formal
 Formalismo operacional ou reconhecedor
 Determinístico
 Não determinístico
 Com movimentos vazios
Autômato Finito
José Couto Júnior - jose.junior@pro.unifacs.br28
 Pode ser representado na forma de um diagrama:
Item Representação
Estados
Entradas ou transições: arcos entre os 
estados, que representam influências externas 
ao sistema
Estado inicial: indicado por uma seta
Estado final ou de aceitação: representado 
por um círculo duplo
Autômato Finito
José Couto Júnior - jose.junior@pro.unifacs.br29
EstadosEstado Inicial Estado Final
Transição
Autômato Finito
José Couto Júnior - jose.junior@pro.unifacs.br30
 Um interruptor
Autômato Finito
José Couto Júnior - jose.junior@pro.unifacs.br31
 Reconhecer abba e babb
Autômato Finito Determinístico
José Couto Júnior - jose.junior@pro.unifacs.br32
Linguagens Regulares
Autômato Finito Determinístico
José Couto Júnior - jose.junior@pro.unifacs.br33
 Autômato Finito Determinístico ou AFD ou DFA e um autômato 
que se encontra sempre em um único estado após ler uma 
sequência qualquer de entrada. 
 O termo “determinístico” implica que existe um e somente um 
estado ao qual o autômato pode transitar a partir de seu estado 
atual
 Para o estado corrente e o símbolo lido da entrada, o sistema 
assume um único estado bem determinado
 Máquina constituída basicamente de:
 Fita: dispositivo de entrada que contém a informação a ser processada 
(cadeia de entrada)
 Unidade de controle: reflete o estado corrente da máquina
 Programa: função que comanda as leituras e o estado da máquina
Autômato Finito Determinístico
José Couto Júnior - jose.junior@pro.unifacs.br34
 Definido pela quíntupla: M = (, Q, d, q0, F), sendo
  = Alfabeto de símbolos de entrada
 Q = Conjunto de estados possíveis do autômato
 d = Função do programa ou programa ou função de 
transição
 d: Q x  Q
 d (p,a) = q
 q0 = Estado inicial
 F = Conjunto de estados finais
d: Q x  Q
d é uma relação entre um estado 
de Q e um símbolo do alfabeto 
que direcionará o controle para 
um estado de Q.
Autômato Finito Determinístico
José Couto Júnior - jose.junior@pro.unifacs.br35
 Definido pela quíntupla: M = (, Q, d, q0, F), sendo
  = {a}
 Q = {q0,q1}
 d (q0,a) = q1
 q0 = q0
 F = {q1}
Qual a linguagem reconhecida por este autômato?
Autômato Finito Determinístico
José Couto Júnior - jose.junior@pro.unifacs.br36
 Considere a seguinte linguagem sobre o alfabeto  = {0,1} e 
construa o autômato que o represente
 L1 = {w 
*| w comece com um 0, seguido de n 1, sendo n 
> 0}
• O autômato reconhece as palavras abaixo?
• 01
• 01111
• 01110
Autômato Finito Determinístico
José Couto Júnior - jose.junior@pro.unifacs.br37
 Considere a seguinte linguagem sobre o alfabeto  = {0,1} e 
construa o autômato que o represente
 L1 = {w 
*| w possua apenas 1 ocorrência de 0}
• O autômato reconhece as palavras abaixo?
• 011
• 11001
• 11011
Autômato Finito Determinístico
José Couto Júnior - jose.junior@pro.unifacs.br38
 Considere a seguinte linguagem sobre o alfabeto  = {0,1} e 
construa o autômato que o represente
 L1 = {w 
*| w possua 01}
• O autômato reconhece as palavras abaixo?
• 011
• 11001
• 1110
• 11011
Autômato Finito Determinístico
José Couto Júnior - jose.junior@pro.unifacs.br39
 Considere a seguinte linguagem sobre o alfabeto  = {a,b} e 
construa o autômato que o represente
 L1 = {w 
*| w possui número ímpar de a}
• O autômato reconhece as palavras abaixo?
• aba
• abaaa
• a
Autômato Finito Determinístico
José Couto Júnior - jose.junior@pro.unifacs.br40
 Considere a seguinte linguagem sobre o alfabeto  = {a,b} e 
construa o autômato que o represente
 L1 = {w 
*| w possui aa ou bb como subpalavra}
Autômato Finito Determinístico
Representação de d
José Couto Júnior - jose.junior@pro.unifacs.br41
 d = Função do programa ou programa ou função de 
transição
 Uma forma comum de representação é através da tabela de 
dupla entrada
d a ...
q0 q1 ...
q1 ... ...
Símbolos do alfabeto
Estados “iniciais”
Estados “finais”
Autômato Finito Determinístico
Representação de d
José Couto Júnior - jose.junior@pro.unifacs.br42
 Defina o autômato abaixo (M = (, Q, d, q0, F) )
  = {a,b}
 Q = {q0,q1,q2,q3}
 q0 = q0
 F = {q3}
d a b
q0
q1
q2
q3
Autômato Finito Determinístico
José Couto Júnior - jose.junior@pro.unifacs.br43
 Considere a seguinte linguagem sobre o alfabeto  = {a,b} e 
construa o autômato que o represente
 L1 = {w 
*| w possui número par de a e número par de 
b}
 Defina o autômato (M = (, Q, d, q0, F) )
Autômato Finito Não Determinístico
José Couto Júnior - jose.junior@pro.unifacs.br44
Linguagens Regulares
Autômato Finito Não Determinístico
José Couto Júnior - jose.junior@pro.unifacs.br45
 Diferentemente dos AFDs , os autômatos finitos não-
determinísticos (AFNs) podem estar em vários estados ao 
mesmo tempo
 Essencial no estudo de modelos de concorrência e linguagens 
formais
 Para o estado corrente e o símbolo lido de entrada, 
determina aleatoriamente um estado de um conjunto de 
estados alternativos
 Uma entrada é aceita se pelo menos um dos caminhos 
alternativos aceita a entrada
Autômato Finito Não Determinístico
José Couto Júnior - jose.junior@pro.unifacs.br46
 Sobre o alfabeto Σ = {0, 1}, consideremos a linguagem 
L = {w ε Σ* | w termina em 01 }.
Teste de aceitação de 00101
Autômato Finito Não Determinístico
José Couto Júnior - jose.junior@pro.unifacs.br47
Teste de aceitação de baba
Autômato Finito Não Determinístico
José Couto Júnior - jose.junior@pro.unifacs.br48
 A cada transição novos caminhos alternativos são possíveis, 
definindo, uma árvore de opções
Autômato Finito Não Determinístico
José Couto Júnior - jose.junior@pro.unifacs.br49
 Definido pela quíntupla: M = (, Q, d, q0, F), sendo
  = Alfabeto de símbolos de entrada
 Q = Conjunto de estados possíveis do autômato
 d = Função do programa ou programa ou função de 
transição
 d: Q x  2Q
 d (p,a) = {q1,q2 ... qn}
 q0 = Estado inicial
 F = Conjunto de estados finais
d: Q x  2Q
d é uma relação entre 
um estado de Q e um 
símbolo do alfabeto
que direcionará o 
controle para n 
estadosde Q.
Autômato Finito Não Determinístico
José Couto Júnior - jose.junior@pro.unifacs.br50
 Considere a seguinte linguagem sobre o alfabeto  = {a,b} e 
construa o autômato que o represente
 L1 = {w 
*| w possui aa ou bb como subpalavra}
 Defina o autômato (M = (, Q, d, q0, F))
d a b
q0 {q0,q1} {q0,q2}
q1 {q3} 
q2  {q3}
q3 {q3} {q3}
M = ({a,b}, {q0,q1,q2,q3}, d, q0, {q3})
Autômato Finito Não Determinístico
José Couto Júnior - jose.junior@pro.unifacs.br51
 Considere a seguinte linguagem sobre o alfabeto  = {0,1}, 
construa o autômato que o represente
 L1 = {w 
*| w possui pelo menos duas ocorrências de 1}
 Defina o autômato (M = (, Q, d, q0, F))
d 0 1
q0 {q0} {q0,q1}
q1 {q1} {q1,q2}
q2 {q2} {q2}
M = ({0,1}, {q0,q1,q2}, d, q0, {q2})
Autômato Finito Não Determinístico
José Couto Júnior - jose.junior@pro.unifacs.br52
 Considere a seguinte linguagem sobre o alfabeto  = {a,b} e 
construa o autômato que o represente
 L1 = {w 
*| w possui aaa como sufixo}
 Defina o autômato (M = (, Q, d, q0, F))
d a b
q0 {q0,q1} {q0}
q1 {q2} 
q2 {q3} 
q3  
M = ({a,b}, {q0,q1,q2,q3}, d, q0, {q3})
Autômato Finito Não Determinístico
José Couto Júnior - jose.junior@pro.unifacs.br53
 Para cada AFN existe um AFD equivalente e vice-versa
 AFN não possui poder computacional maior que o AFD
Autômato Finito Não Determinístico
José Couto Júnior - jose.junior@pro.unifacs.br54
 Construa o AFD equivalente ao autômato anterior
d a b
q0 {q1} {q0}
q1 {q2} {q0}
q2 {q3} {q0}
q3 {q3} {q0}
M = ({a,b}, {q0,q1,q2,q3}, d, q0, {q3})
Autômato Finito com movimentos vazios
José Couto Júnior - jose.junior@pro.unifacs.br55
Linguagens Regulares
Autômato Finito com movimentos 
vazios
José Couto Júnior - jose.junior@pro.unifacs.br56
 Movimentos vazios generalizam os movimentos não 
determinísticos
 Movimento vazio é uma transição sem leitura de símbolos
 Facilitam construções e demonstrações relacionadas com os 
autômatos
 Movimento vazio é representado pela letra Ɛ
Autômato Finito com movimentos 
vazios
José Couto Júnior - jose.junior@pro.unifacs.br57
 Considere a seguinte linguagem sobre o alfabeto  = {a,b} e 
construa o autômato que o represente
 L1 = {w 
*| w é sequência de a seguida de sequência de 
b}
 Defina o autômato (M = (, Q, d, q0, F))
d a b Ɛ
q0 {q0}  {q1}
q1  {q1} 
M = ({a,b}, {q0,q1}, d, q0, {q1})
Expressões Regulares
José Couto Júnior - jose.junior@pro.unifacs.br58
Linguagens Regulares
Expressões Regulares
José Couto Júnior - jose.junior@pro.unifacs.br59
 Toda linguagem regular pode ser descrita por uma expressão 
regular
 Formalismo denotacional gerador, uma vez que se pode 
inferir como gerar as palavras de uma linguagem
 Definida a partir de 
 Conjuntos básicos
 Operações de concatenação e união
 Adequadas para comunicação homem X máquina
Expressões Regulares
José Couto Júnior - jose.junior@pro.unifacs.br60
 Definições:
  linguagem vazia
 Ɛ  palavra vazia
 {Ɛ}  linguagem possui exclusivamente a palavra vazia
 {x}  linguagem contém exclusivamente a palavra x, sendo 
x
Expressões Regulares
José Couto Júnior - jose.junior@pro.unifacs.br61
 Sendo r e s expressões regulares que denotam as linguagem 
R e S, respectivamente, então:
 União: (r + s) denota a linguagem R  S 
 Concatenação (rs): denota a linguagem RS = {uv | u  R e v 
S}
 Concatenação sucessiva: (r*) denota a linguagem R*
 Convenções:
 A concatenação sucessiva tem precedência sobre a concatenação 
e a união
 A concatenação tem precedência sobre a união
Expressões Regulares
José Couto Júnior - jose.junior@pro.unifacs.br62
Expressão Regular Linguagem Gerada
aa
ba*
(a+b)*
(a+b)*aa(a+b)*
a*ba*ba*
(a+b)*(aa+bb)
(a+Ɛ)(b+ba)*
Expressões Regulares
José Couto Júnior - jose.junior@pro.unifacs.br63
Expressão Regular Linguagem Gerada
aa Somente a palavra aa
ba*
(a+b)*
(a+b)*aa(a+b)*
a*ba*ba*
(a+b)*(aa+bb)
(a+Ɛ)(b+ba)*
Expressões Regulares
José Couto Júnior - jose.junior@pro.unifacs.br64
Expressão Regular Linguagem Gerada
aa Somente a palavra aa
ba* Todas as palavras iniciadas por b, seguido de zero ou 
mais a
(a+b)*
(a+b)*aa(a+b)*
a*ba*ba*
(a+b)*(aa+bb)
(a+Ɛ)(b+ba)*
Expressões Regulares
José Couto Júnior - jose.junior@pro.unifacs.br65
Expressão Regular Linguagem Gerada
aa Somente a palavra aa
ba* Todas as palavras iniciadas por b, seguido de zero ou 
mais a
(a+b)* Todas as palavras sobre o alfabeto {a,b}
(a+b)*aa(a+b)*
a*ba*ba*
(a+b)*(aa+bb)
(a+Ɛ)(b+ba)*
Expressões Regulares
José Couto Júnior - jose.junior@pro.unifacs.br66
Expressão Regular Linguagem Gerada
aa Somente a palavra aa
ba* Todas as palavras iniciadas por b, seguido de zero ou 
mais a
(a+b)* Todas as palavras sobre o alfabeto {a,b}
(a+b)*aa(a+b)* Todas as palavras que contenham aa como subpalavra
a*ba*ba*
(a+b)*(aa+bb)
(a+Ɛ)(b+ba)*
Expressões Regulares
José Couto Júnior - jose.junior@pro.unifacs.br67
Expressão Regular Linguagem Gerada
aa Somente a palavra aa
ba* Todas as palavras iniciadas por b, seguido de zero ou 
mais a
(a+b)* Todas as palavras sobre o alfabeto {a,b}
(a+b)*aa(a+b)* Todas as palavras que contenham aa como subpalavra
a*ba*ba* Todas as palavras que contenham exatamente dois b
(a+b)*(aa+bb)
(a+Ɛ)(b+ba)*
Expressões Regulares
José Couto Júnior - jose.junior@pro.unifacs.br68
Expressão Regular Linguagem Gerada
aa Somente a palavra aa
ba* Todas as palavras iniciadas por b, seguido de zero ou 
mais a
(a+b)* Todas as palavras sobre o alfabeto {a,b}
(a+b)*aa(a+b)* Todas as palavras que contenham aa como subpalavra
a*ba*ba* Todas as palavras que contenham exatamente dois b
(a+b)*(aa+bb) Todas as palavras que terminem com aa ou bb
(a+Ɛ)(b+ba)*
Expressões Regulares
José Couto Júnior - jose.junior@pro.unifacs.br69
Expressão Regular Linguagem Gerada
aa Somente a palavra aa
ba* Todas as palavras iniciadas por b, seguido de zero ou 
mais a
(a+b)* Todas as palavras sobre o alfabeto {a,b}
(a+b)*aa(a+b)* Todas as palavras que contenham aa como subpalavra
a*ba*ba* Todas as palavras que contenham exatamente dois b
(a+b)*(aa+bb) Todas as palavras que terminem com aa ou bb
(a+Ɛ)(b+ba)* Todas as palavras que não possuem dois a 
consecutivos
Expressões Regulares
José Couto Júnior - jose.junior@pro.unifacs.br70
 Descreva em palavras as linguagens geradas pelas seguintes 
expressões regulares
 (a+b+c)*(a+b+c)
 (aa+b)*(a+bb)
 (b+ab)*(Ɛ+a)
 ((b+c)*+a(b+c)*a)*
Qualquer sequência de a, b e c, com pelo menos um caracter
Qualquer sequência de a e b que não tenha dois a’s seguidos
Qualquer sequência de a, b e c que contenha número par de a’s
Qualquer sequência de aa e b, finalizada por a ou bb
 Construa AFNs que representem as expressões abaixo:
 (a+b+c)*(a+b+c)
 (aa+b)*(a+bb)
 (b+ab)*(Ɛ+a)
 ((b+c)*+a(b+c)*a)*
Expressões Regulares
José Couto Júnior - jose.junior@pro.unifacs.br71
 Construa AFNs que representem as expressões abaixo:
 (a+b+c)*(a+b+c)
 (aa+b)*(a+bb)
 (b+ab)*(Ɛ+a)
 ((b+c)*+a(b+c)*a)*
Expressões Regulares
José Couto Júnior - jose.junior@pro.unifacs.br72
 Construa AFNs que representem as expressões abaixo:
 (a+b+c)*(a+b+c)
 (aa+b)*(a+bb)
 (b+ab)*(Ɛ+a)
 ((b+c)*+a(b+c)*a)*
Expressões Regulares
José Couto Júnior - jose.junior@pro.unifacs.br73
 Construa AFNs que representem as expressões abaixo:
 (a+b+c)*(a+b+c)
 (aa+b)*(a+bb)
 (b+ab)*(Ɛ+a)
 ((b+c)*+a(b+c)*a)*
Expressões RegularesJosé Couto Júnior - jose.junior@pro.unifacs.br74
Atividade em sala
José Couto Júnior - jose.junior@pro.unifacs.br75
 Qual a linguagem que é gerada pelas gramática abaixo?
L(G) = {anbc | n ≥ 0}
G = ( {Dig, Int }, {+, -, 0, ..., 9}, P, Int) 
P = { Int +Dig | -Dig
Dig 0Dig | 1Dig|...| 9Dig
Dig | 0 | 1 | 2 |...|9 }
G = ({S, A}, {a, b, c}, P, S) 
P = { S  aS | bA
A  c }
L(G) = conj. números inteiros 
com sinal ±[0..9]+
Atividade em sala
José Couto Júnior - jose.junior@pro.unifacs.br76
 Qual a linguagem que é gerada pela gramática abaixo?
L(G) = {0(10)*}
G = ( {A,B,C}, {0,1}, P, A) 
P = { A  0B | 0
B  1C 
C  0B | 0 }
Atividade em sala
José Couto Júnior - jose.junior@pro.unifacs.br77
 Classifique as gramáticas, dê a quádrupla e a L(G) e diga se as 
linguagens são finitas/infinitas 
E  E + E | E - E | E * E | E / E | (E) | F 
F  0 | 1 | ... | 9 
A  BC 
BC  CB 
B  b 
C  a
S  0A 
A  1S | 1
Gram. Livre de Contexto
G = ( {E,F}, 
{0,1,2...9},
P, E)
Linguagem infinitaGram. Sensível ao Contexto
G = ( {A,B,C}, 
{a,b},
P, A)
Linguagem finita
Gram. Regular
G = ( {S,A}, 
{0,1},
P, S)
Linguagem infinita
Atividade em sala
José Couto Júnior - jose.junior@pro.unifacs.br78
 Qual a gramática das linguagens abaixo?
L(G6) = {111(00)n | n >= 0}
S  111B
B  00B | Ɛ
G = ( {S,B}, 
{1,0},
P, S)
Gramáticas Regulares
José Couto Júnior - jose.junior@pro.unifacs.br79
Linguagens Regulares
Gramáticas Regulares
José Couto Júnior - jose.junior@pro.unifacs.br80
 Um gramática é dita regular (GR) se esta é uma gramática 
linear
 Uma gramática linear pode ser classificada em:
 Gramática linear à direita: Se todas as regras de produção são do 
tipo A tN ou A t
 Gramática linear à esquerda: Se todas as regras de produção são 
do tipo A Nt ou A t
 Gramática linear unitária à direita: Se todas as regras de 
produção são como na linear à direita e, adicionalmente |t| < 1
 Gramática linear unitária à esquerda: Se todas as regras de 
produção são como na linear à esquerda e, adicionalmente |t| 
< 1
Gramáticas Regulares
José Couto Júnior - jose.junior@pro.unifacs.br81
 A linguagem a(ba)* é gerada pelas seguintes GR
 Gramática linear à direita: G = ({S,A},{a,b},P,S)
 Gramática linear à esquerda: G = ({S},{a,b},P,S)
 Gramática linear unitária à direita: G = ({S,A,B},{a,b},P,S)
 Gramática linear unitária à esquerda: G = ({S,A},{a,b},P,S)
S  aA
A  baA | Ɛ
S  Sba | a
S  aA
A  bB | Ɛ
B  aA
S Aa | a
A  Sb
Equivalência e minimização de autômatos
José Couto Júnior - jose.junior@pro.unifacs.br82
Linguagens Regulares
Operação complemento
José Couto Júnior - jose.junior@pro.unifacs.br83
 Visa identificar todas as palavras que não são reconhecidas 
por uma linguagem, ou seja, o que complementa a linguagem 
original
 Uma linguagem L tem seu complemento representado por 
~L
 Passos para a construção do autômato de complemento
 Cria um estado não final d
 Todas as transições indefinidas serão direcionadas ao estado d
 Crie um ciclo em d para todos os símbolos do alfabeto
 Transforme os estados finais em não finais e vice-versa
Operação complemento
José Couto Júnior - jose.junior@pro.unifacs.br84
 Cria um estado não final d
 Todas as transições indefinidas serão direcionadas ao estado d
Operação complemento
José Couto Júnior - jose.junior@pro.unifacs.br85
 Crie um ciclo em d para todos os símbolos do alfabeto
 Transforme os estados finais em não finais e vice-versa
Operação complemento
José Couto Júnior - jose.junior@pro.unifacs.br86
 L
 ~L
Equivalência
José Couto Júnior - jose.junior@pro.unifacs.br87
 Dois AF são equivalentes se reconhecem a mesma linguagem
 M1 e M2 são autômatos finitos e ACEITA(M1) = 
ACEITA(M2), então existe um M3 tal que ACEITA(M3) 
 L3 = (L1  ~L2)  (~L1  L2)
 L1 = L2 se, e somente se, L3 for vazia
Equivalência entre AFN e AFD
José Couto Júnior - jose.junior@pro.unifacs.br88
 Um autômato finito não determinístico pode se transformar 
em um autômato finito determinístico equivalente
 Dois autômatos são considerados equivalentes se aceitam a 
mesma linguagem
Equivalência entre AFN e AFD
José Couto Júnior - jose.junior@pro.unifacs.br89
 Para construir um AFD a partir de um AFN qualquer, devemos 
realizar os seguintes passos: 
1. Construir a tabela de transições do AFN(j)
2. Construir a tabela de transições do AFD (δ) através do produto 
cartesiano dos estados de j, incluindo como último o conjunto o 
vazio
3. Mostrar todos os conjuntos que contém como elemento estados 
finais como novo estado final de δ
4. Verificar a ocorrência de cada conjunto de δ em relação a um 
símbolo e colocar como resultado o conjunto correspondente que 
pertence a δ. Quando existir mais de um elemento no conjunto a 
ocorrência passa a ser a união das ocorrências de todas as 
transições. 
5. Eliminar as linhas que possuem transições somente com saídas (não 
existe transição que chega até ela, isto é, estado inacessível).
Equivalência entre AFN e AFD
José Couto Júnior - jose.junior@pro.unifacs.br90
6. Montar o AFD a partir de δ.
7. Eliminar os estados que não possuem saída para outro estado 
e não são finais. 
8. Verificar se uma cadeia que pertencia ao AFN também 
pertence ao AFD gerado
Equivalência entre AFN e AFD
José Couto Júnior - jose.junior@pro.unifacs.br91
 Considere o AFN abaixo e construa o AFD equivalente
1. Construir a tabela de transições do AFN(j)
j a b
q0 {q1,q2} -
q1 {q2} {q0,q2}
q2 {q2} {q0}
Equivalência entre AFN e AFD
José Couto Júnior - jose.junior@pro.unifacs.br92
 Considere o AFN abaixo e construa o AFD equivalente
2. Construir a tabela de transições do AFD 
(δ) através do produto cartesiano dos 
estados de j, incluindo como último o 
conjunto o vazio
δ a b
S0 = {q0} 
S1 = {q1} 
S2 = {q2} 
S3 = {q0, q1}
S4 = {q0, q2}
S5 = {q1, q2}
S6 = {q0, q1, q2}
S7 = { } 
Equivalência entre AFN e AFD
José Couto Júnior - jose.junior@pro.unifacs.br93
 Considere o AFN abaixo e construa o AFD equivalente
3. Mostrar todos os conjuntos que contém 
como elemento estados finais como novo 
estado final de δ
δ a b
S0 = {q0} 
S1 = {q1} 
S2 = {q2} 
S3 = {q0, q1}
S4 = {q0, q2}
S5 = {q1, q2}
S6 = {q0, q1, q2}
S7 = { } 
Equivalência entre AFN e AFD
José Couto Júnior - jose.junior@pro.unifacs.br94
 Considere o AFN abaixo e construa o AFD equivalente
4. Verificar a ocorrência de cada conjunto de δ em relação a um 
símbolo e colocar como resultado o conjunto correspondente 
que pertence a δ. Quando existir mais de um elemento no 
conjunto a ocorrência passa a ser a união das ocorrências de 
todas as transições. 
δ a b
S0 = {q0} S5 S7
S1 = {q1} S2 S4
S2 = {q2} S2 S0
S3 = {q0, q1} S5 S4
S4 = {q0, q2} S5 S0
S5 = {q1, q2} S2 S4
S6 = {q0, q1, q2} S5 S4
S7 = { } S7 S7
Equivalência entre AFN e AFD
José Couto Júnior - jose.junior@pro.unifacs.br95
 Considere o AFN abaixo e construa o AFD equivalente
5. Eliminar as linhas que possuem 
transições somente com saídas (não 
existe transição que chega até ela, isto é, 
estado inacessível). 
δ a b
S0 = {q0} S5 S7
S1 = {q1} S2 S4
S2 = {q2} S2 S0
S3 = {q0, q1} S5 S4
S4 = {q0, q2} S5 S0
S5 = {q1, q2} S2 S4
S6 = {q0, q1, q2} S5 S4
S7 = { } S7 S7
Equivalência entre AFN e AFD
José Couto Júnior - jose.junior@pro.unifacs.br96
 Considere o AFN abaixo e construa o AFD equivalente
5. Eliminar as linhas que possuem 
transições somente com saídas (não 
existe transição que chega até ela, isto é, 
estadoinacessível). 
δ a b
S0 = {q0} S5 S7
S2 = {q2} S2 S0
S4 = {q0, q2} S5 S0
S5 = {q1, q2} S2 S4
S7 = { } S7 S7
Equivalência entre AFN e AFD
José Couto Júnior - jose.junior@pro.unifacs.br97
 Considere o AFN abaixo e construa o AFD equivalente
6. Montar o AFD a partir de δ. 
δ a b
S0 = {q0} S5 S7
S2 = {q2} S2 S0
S4 = {q0, q2} S5 S0
S5 = {q1, q2} S2 S4
S7 = { } S7 S7
Equivalência entre AFN e AFD
José Couto Júnior - jose.junior@pro.unifacs.br98
 Considere o AFN abaixo e construa o AFD equivalente
7. Eliminar os estados que não possuem 
saída para outro estado e não são finais.
δ a b
S0 = {q0} S5 S7
S2 = {q2} S2 S0
S4 = {q0, q2} S5 S0
S5 = {q1, q2} S2 S4
S7 = { } S7 S7
Equivalência entre AFN e AFD
José Couto Júnior - jose.junior@pro.unifacs.br99
 Considere o AFN abaixo e construa o AFD equivalente
8. Verificar se uma cadeia que pertencia ao AFN também pertence 
ao AFD gerado.
ababaaba
AFN: q0 q1 q0 q1 q0 q1 q2 q0 q2
AFD: S0 S5 S4 S5 S4 S5 S2 S0 S5
 Transforme os AFNs em AFDs
 Represente os complementos dos AFDs
Equivalência entre AFN e AFD
José Couto Júnior - jose.junior@pro.unifacs.br100
Minimização de autômatos
José Couto Júnior - jose.junior@pro.unifacs.br102
 Objetivo: gerar um AF equivalente com o menor número de 
estados possível, denominado autômato finito mínimo
 Atuará sobre os Estados equivalentes
 Dois estados são equivalentes se o processamento de uma entrada 
qualquer resulta na mesma condição ACEITA/REJEITA
 Dois autômatos distintos que aceitam a mesma linguagem, ao 
serem minimizados, geram o mesmo autômato finito mínimo
 Obs:
 O tempo de processamento de um AFD é diretamente proporcional 
ao tamanho da entrada
 O número de estados não interfere no tempo de processamento de 
uma entrada
Minimização de autômatos
José Couto Júnior - jose.junior@pro.unifacs.br103
 Um AF a ser minimizado deve atender aos seguintes pré-
requisitos:
 Deve ser determinístico
 Não pode ter estados inacessíveis
 A função programa deve ser total (a partir de qualquer estado, 
são previstas transições para todos os símbolos do alfabeto)
 Para atender ao último requisito
 Criar um estado não final d
 Incluir as transições não previstas tendo d como estado destino
 Incluir um ciclo em d para todos os símbolos do alfabeto
Minimização de autômatos
José Couto Júnior - jose.junior@pro.unifacs.br104
 Consideremos o autômato ao lado. 
1. É determinístico?
2. Tem estados inacessíveis?
3. A função programa é total?
Minimização de autômatos
José Couto Júnior - jose.junior@pro.unifacs.br105
1. Construir tabela relacionando os 
estados distintos
q1
q2
q3
q4
q5
q0 q1 q2 q3 q4
q1
q2
q3
q4
q5
q0 q1 q2 q3 q4
Minimização de autômatos
José Couto Júnior - jose.junior@pro.unifacs.br106
2. Marcar todos os pares do tipo 
{estado final, estado não final} 
estes estados não são equivalentes
q1 X
q2 X
q3 X
q4 X X X
q5 X X X
q0 q1 q2 q3 q4
Minimização de autômatos
José Couto Júnior - jose.junior@pro.unifacs.br107
3. Análise dos pares não marcados, os 
quais podem ser equivalentes
q1 X
q2 X
q3 X
q4 X X X
q5 X X X
q0 q1 q2 q3 q4
1. {q0,q4}
2. {q0,q5}
3. {q1,q2}
4. {q1,q3}
5. {q2,q3}
6. {q4,q5}
Minimização de autômatos: Análise 
dos pares não marcados
José Couto Júnior - jose.junior@pro.unifacs.br108
 Para cada par {qu, qv} não marcado e para cada símbolo a
, suponha que 
 d(qu,a) = pu e d (qv,a) = pv, então
 Se pu = pv, então qu e qv são equivalentes para o símbolo a e não 
devem ser marcados
 Se pu ≠ pv e o par {pu,pv} não está marcado, então {qu,qv} é 
incluído em uma lista a partir de {pu,pv} para análise posterior
 Se pu ≠ pv e o par {pu,pv} está marcado, então
 {qu,qv} não é equivalente e deve ser marcado
 Se {qu,qv} encabeça uma lista de pares, então marcar todos os pares da 
lista (e, recursivamente, se algum par da lista encabeça outra lista)
Minimização de autômatos
José Couto Júnior - jose.junior@pro.unifacs.br109
3. Análise dos pares não marcados, os 
quais podem ser equivalentes
q1 X
q2 X
q3 X
q4 X X X
q5 X X X
q0 q1 q2 q3 q4
1. {q0,q4} 
d(q0,a) = q2 d(q0,b) = q1
d(q4,a) = q3 d(q4,b) = q2
Minimização de autômatos
José Couto Júnior - jose.junior@pro.unifacs.br110
3. Análise dos pares não marcados, os quais podem ser equivalentes
1. {q0,q4}  d(q0,a) = q2 d(q0,b) = q1
d(q4,a) = q3 d(q4,b) = q2
Se pu ≠ pv e o par {pu,pv} não está
marcado, então {qu,qv} é incluído
em uma lista a partir de {pu,pv}
para análise posterior
Se pu ≠ pv e o par {pu,pv} não
está marcado, então {qu,qv} é
incluído em uma lista a partir de
{pu,pv} para análise posterior
(q2,q3)  (q0,q4) (q1,q2)  (q0,q4)
Minimização de autômatos
José Couto Júnior - jose.junior@pro.unifacs.br111
3. Análise dos pares não marcados, os 
quais podem ser equivalentes
q1 X
q2 X
q3 X
q4 X X X
q5 X X X
q0 q1 q2 q3 q4
1. {q0,q4} 
1. (q2,q3)  (q0,q4)
2. (q1,q2)  (q0,q4)
2. {q0,q5}
Minimização de autômatos
José Couto Júnior - jose.junior@pro.unifacs.br112
3. Análise dos pares não marcados, os quais podem ser equivalentes
1. {q0,q5}  d(q0,a) = q2 d(q0,b) = q1
d(q5,a) = q2 d(q5,b) = q3
Se pu = pv, então qu e qv são 
equivalentes para o símbolo a e 
não devem ser marcados
Se pu ≠ pv e o par {pu,pv} não
está marcado, então {qu,qv} é
incluído em uma lista a partir de
{pu,pv} para análise posterior
(q1,q3)  (q0,q5)
Minimização de autômatos
José Couto Júnior - jose.junior@pro.unifacs.br113
3. Análise dos pares não marcados, os 
quais podem ser equivalentes
q1 X
q2 X
q3 X
q4 X X X
q5 X X X
q0 q1 q2 q3 q4
1. {q0,q4} 
1. (q2,q3)  (q0,q4)
2. (q1,q2)  (q0,q4)
2. {q0,q5}
1. (q1,q3)  (q0,q5)
3. {q1,q2}
Minimização de autômatos
José Couto Júnior - jose.junior@pro.unifacs.br114
3. Análise dos pares não marcados, os quais podem ser equivalentes
1. {q1,q2}  d(q1,a) = q1 d(q1,b) = q0
d(q2,a) = q4 d(q2,b) = q5
Se pu ≠ pv e o par {pu,pv} não
está marcado, então {qu,qv} é
incluído em uma lista a partir de
{pu,pv} para análise posterior
(q0,q5)  (q1,q2)
Se pu ≠ pv e o par {pu,pv} está 
marcado, então
• {qu,qv} não é equivalente e 
deve ser marcado
• Se {qu,qv} encabeça uma lista 
de pares, então marcar todos 
os pares da lista (e, 
recursivamente, se algum par 
da lista encabeça outra lista)
Minimização de autômatos
José Couto Júnior - jose.junior@pro.unifacs.br115
3. Análise dos pares não marcados, os 
quais podem ser equivalentes
q1 X
q2 X 
q3 X
q4  X X X
q5 X X X
q0 q1 q2 q3 q4
1. {q0,q4} 
1. (q2,q3)  (q0,q4)
2. (q1,q2)  (q0,q4)
2. {q0,q5}
1. (q1,q3)  (q0,q5)
3. {q1,q2}
1. (q0,q5)  (q1,q2)
4. {q1,q3}
Minimização de autômatos
José Couto Júnior - jose.junior@pro.unifacs.br116
3. Análise dos pares não marcados, os quais podem ser equivalentes
1. {q1,q3}  d(q1,a) = q1 d(q1,b) = q0
d(q3,a) = q5 d(q3,b) = q4
Se pu ≠ pv e o par {pu,pv} está 
marcado, então
• {qu,qv} não é equivalente e 
deve ser marcado
• Se {qu,qv} encabeça uma lista 
de pares, então marcar todos os 
pares da lista (e, 
recursivamente, se algum par da 
lista encabeça outra lista)
Minimização de autômatos
José Couto Júnior - jose.junior@pro.unifacs.br117
3. Análise dos pares não marcados, os 
quais podem ser equivalentes
q1 X
q2 X 
q3 X 
q4  X X X
q5  X X X
q0 q1 q2 q3 q4
1. {q0,q4} 
1. (q2,q3)  (q0,q4)
2. (q1,q2)  (q0,q4)
2. {q0,q5}
1. (q1,q3)  (q0,q5)
3. {q1,q2}
1. (q0,q5)  (q1,q2)4. {q1,q3}
5. {q2,q3}
Minimização de autômatos
José Couto Júnior - jose.junior@pro.unifacs.br118
3. Análise dos pares não marcados, os quais podem ser equivalentes
1. {q2,q3}  d(q2,a) = q4 d(q2,b) = q5
d(q3,a) = q5 d(q3,b) = q4
Se pu ≠ pv e o par {pu,pv} não está
marcado, então {qu,qv} é incluído em
uma lista a partir de {pu,pv} para
análise posterior
Se pu ≠ pv e o par {pu,pv}
não está marcado, então
{qu,qv} é incluído em uma
lista a partir de {pu,pv} para
análise posterior
(q4,q5)  (q2,q3) (q4,q5)  (q2,q3)
Minimização de autômatos
José Couto Júnior - jose.junior@pro.unifacs.br119
3. Análise dos pares não marcados, os 
quais podem ser equivalentes
q1 X
q2 X 
q3 X 
q4  X X X
q5  X X X
q0 q1 q2 q3 q4
1. {q0,q4} 
1. (q2,q3)  (q0,q4)
2. (q1,q2)  (q0,q4)
2. {q0,q5}
1. (q1,q3)  (q0,q5)
3. {q1,q2}
1. (q0,q5)  (q1,q2)
4. {q1,q3}
5. {q2,q3}
1. (q4,q5)  (q2,q3)
6. {q4,q5}
Minimização de autômatos
José Couto Júnior - jose.junior@pro.unifacs.br120
3. Análise dos pares não marcados, os quais podem ser equivalentes
1. {q4,q5}  d(q4,a) = q3 d(q4,b) = q2
d(q5,a) = q2 d(q5,b) = q3
Se pu ≠ pv e o par {pu,pv} não está
marcado, então {qu,qv} é incluído em
uma lista a partir de {pu,pv} para
análise posterior
Se pu ≠ pv e o par {pu,pv}
não está marcado, então
{qu,qv} é incluído em uma
lista a partir de {pu,pv} para
análise posterior
(q2,q3)  (q4,q5) (q2,q3)  (q4,q5)
Minimização de autômatos
José Couto Júnior - jose.junior@pro.unifacs.br121
3. Análise dos pares não marcados, os 
quais podem ser equivalentes
q1 X
q2 X 
q3 X 
q4  X X X
q5  X X X
q0 q1 q2 q3 q4
1. {q0,q4} 
1. (q2,q3)  (q0,q4)
2. (q1,q2)  (q0,q4)
2. {q0,q5}
1. (q1,q3)  (q0,q5)
3. {q1,q2}
1. (q0,q5)  (q1,q2)
4. {q1,q3}
5. {q2,q3}
1. (q4,q5)  (q2,q3)
6. {q4,q5}
1. (q2,q3)  (q4,q5)
Minimização de autômatos
José Couto Júnior - jose.junior@pro.unifacs.br122
q1 X
q2 X 
q3 X 
q4  X X X
q5  X X X
q0 q1 q2 q3 q4
4. Unificar os estados equivalente: os 
estados não marcados são 
equivalentes e devem ser unificados 
conforme regras:
1. Se os estados são não finais, a 
unificação será um estado não final
2. Se os estados são finais, a unificação 
será um estado não final
3. Se algum estado for inicial, então o 
correspondente será inicial
4. Todas as transições devem ser 
preservadas, mas passam a ter 
origem-destino no estado unificado
Minimização de autômatos
José Couto Júnior - jose.junior@pro.unifacs.br123
q1 X
q2 X 
q3 X 
q4  X X X
q5  X X X
q0 q1 q2 q3 q4
Minimização de autômatos:
Resumo
José Couto Júnior - jose.junior@pro.unifacs.br124
 Verificações: 
1. É determinístico?
2. Tem estados inacessíveis?
3. A função programa é total?
 Construir tabela relacionando os 
estados distintos
 Marcar todos os pares do tipo 
{estado final, estado não final} 
estes estados não são equivalentes
 Análise dos pares não marcados, 
os quais podem ser equivalentes
 Para cada par {qu, qv} não marcado e 
para cada símbolo a , suponha que 
 d(qu,a) = pu e d (qv,a) = pv, então
 Se pu = pv, então qu e qv são 
equivalentes para o símbolo a e não 
devem ser marcados
 Se pu ≠ pv e o par {pu,pv} não está 
marcado, então {qu,qv} é incluído em 
uma lista a partir de {pu,pv} para 
análise posterior
 Se pu ≠ pv e o par {pu,pv} está 
marcado, então
 {qu,qv} não é equivalente e deve ser 
marcado
 Se {qu,qv} encabeça uma lista de pares, 
então marcar todos os pares da lista (e, 
recursivamente, se algum par da lista 
encabeça outra lista)
 Minimize os autômatos abaixo
Minimização de autômatos:
José Couto Júnior - jose.junior@pro.unifacs.br125
Respostas
José Couto Júnior - jose.junior@pro.unifacs.br126