Buscar

Linguagens Formais e Automatos - Slides do curso completo

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

Slides/LFA.2015.2.Aula01.Introdu��o.pdf
Aula 01 - Introdução
Linguagens Formais e 
Autômatos
Prof. Dr. Daniel Lucrédio
Departamento de Computação / UFSCar
Última revisão: ago/2015
Referências bibliográficas
● Introdução à teoria dos autômatos, linguagens e computação / John 
E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman ; tradução da 2.ed. 
original de Vandenberg D. de Souza. - Rio de Janeiro : Elsevier, 2002 
(Tradução de: Introduction to automata theory, languages, and 
computation - ISBN 85-352-1072-5)
○ Capítulo 1 - Seções 1.1 e 1.5
● Introdução à teoria da computação / Michael Sipser ; tradução técnica 
Ruy José Guerra Barretto de Queiroz ; revisão técnica Newton José Vieira. 
-- São Paulo : Thomson Learning, 2007 (Título original : Introduction to the 
theory of computation. "Tradução da segunda edição norte-americana" - 
ISBN 978-85-221-0499-4)
○ Capítulo 0 - Seção 0.1
Introdução
Autômatos
Computabilidade
Complexidade
Quais são as 
capacidades e 
limitações 
fundamentais dos 
computadores?
Introdução
● Década de 1930
● Matemáticos
● Antes da existência dos computadores
Teoria da complexidade
● Alguns problemas são simples
○ Ordenação
● Outros são complexos
○ Escalonamento de aulas em uma universidade
○ 1000 aulas: o tempo para achar o melhor 
escalonamento pode levar séculos
○ Número com 500 dígitos: fatorar leva todo o tempo 
de vida do universo
O que torna alguns problemas computacionalmente 
difíceis e outros fáceis?
Teoria da complexidade
● Não sabemos a resposta!
● Mas temos um esquema para classificar problemas 
conforme sua dificuldade
● Várias opções...
○ Alterar o problema (ou aquele aspecto)
○ Contentar-se com uma solução menos do que 
perfeita
○ Alguns problemas só são difíceis no pior caso
● Ex: criptografia
Teoria da computabilidade
● Alguns problemas não podem ser resolvidos por 
computadores
○ Ex: um enunciado matemático é verdadeiro ou 
falso?
● Problemas solúveis vs insolúveis
Teoria dos autômatos
● Definições e propriedades de modelos matemáticos 
de computação
● Autômatos são abstrações matemáticas que 
ajudam a entender este modelo
○ Tem implicações e aplicações práticas
Autômatos e Linguagens
Autômatos e Linguagens
● Conceitos centrais
● Alfabeto: conjunto finito, não vazio, de símbolos
○ Símbolos = membros de um alfabeto
● Ʃ (sigma) ou Γ (gamma)
○ Ex: Ʃ = {0,1}
○ Ʃ = {a,b,c,...,z}
○ Ʃ = conjunto de caracteres ASCII
Autômatos e Linguagens
● Cadeia/string sobre um alfabeto
○ Sequência finita de símbolos daquele alfabeto
○ Geralmente escritos um seguido do outro e não 
separados por vírgulas
● Ex: 01001, if, then, while
● Se w é uma cadeia sobre Ʃ, o comprimento de uma 
cadeia |w| é o número de símbolos que ela contém
○ Estritamente, é o número de posições que conta
● Cadeia de comprimento zero
○ ε (epsilon minúsculo)
Autômatos e Linguagens
● Se w tem comprimento n
○ w = w1w2...wn, onde cada wi ∈ Ʃ
● Reverso de w = wR
○ Cadeia obtida escrevendo-se w na ordem inversa
○ wnwn-1...w1 
● z é uma subcadeia/substring de w se z aparece 
consecutivamente dentro de w
○ cad é uma subcadeia de abracadabra
Autômatos e Linguagens
● Cadeia x de comprimento m
● Cadeia y de comprimento n
● Concatenação de x e y, escrito xy é:
○ x1x2...xmy1y2...yn
○ |xy|=m+n
○ xx...x = xk
○ wε=εw=w
Autômatos e Linguagens
● Potências de um alfabeto
● Ʃk
○ Conjunto de cadeias de comprimento k, e o símbolo de 
cada um deles está em Ʃ
● Ʃ0={ε} (independente do alfabeto)
● Se Ʃ={0,1}
○ Ʃ1={0,1}
○ Ʃ2={00,01,10,11}
○ Ʃ3={000,001,010,011,100,101,110,111}
○ Ʃ*=conjunto de todas as cadeias sobre um alfabeto
○ Ʃ*= Ʃ0 ∪ Ʃ1 ∪ Ʃ2 ∪ ...
○ Ʃ+= Ʃ1 ∪ Ʃ2 ∪ ...
○ Ʃ* = Ʃ+ ∪ {ε}
Linguagens
● Um conjunto de cadeias escolhidas de um alfabeto
○ Se Ʃ é um alfabeto
○ L ⊆ Ʃ*
○ L é uma linguagem sobre Ʃ
■ E sobre qualquer alfabeto que contenha Ʃ
● Outras conclusões
○ Ʃ* é uma linguagem para qualquer alfabeto Ʃ
○ ∅ (linguagem vazia) é uma linguagem sobre 
qualquer alfabeto
○ {ε} é uma linguagem sobre qualquer alfabeto
Linguagens e Problemas
● O termo “linguagem” pode parecer estranho
○ Mas linguagens comuns podem ser vistas como um 
conjunto de cadeias
○ Ex: português/alfabeto latino, grego/alfabeto grego
○ Ex: C/ASCII
● Exemplos mais abstratos
○ Ex: Linguagens de todas as cadeias que consistem 
de n 0’s seguidos por n 1’s
○ Ex: Conjunto de cadeias com número igual de 0’s e 
1’s
Linguagens
● Linguagens podem possuir infinitas palavras, mas 
alfabetos são finitos
● Problemas: na teoria dos autômatos, um problema 
é a decisão sobre se uma dada cadeia/palavra é 
parte de uma linguagem particular
○ Se Ʃ é um alfabeto, e L é uma linguagem sobre Ʃ, 
então um problema (formal) é:
■ Dada uma string w em Ʃ*, decidir se w pertence ou não a L
● Também enquadra a noção coloquial de problema
Linguagens e Problemas
● Linguagens podem descrever situações reais
○ Ex: uma linguagem que descreve os caminhos entre 
minha casa e o trabalho:
■ DDEEFFDED (a cada esquina)
■ Há vários caminhos (cadeias)
○ Problema: encontrar o caminho mais curto
■ Ou: dado um caminho, é o mais curto?
■ Ou: encontre todos os caminhos até a minha casa
● Em termos da teoria da computação, são a mesma 
coisa
○ A dificuldade – em essência – é a mesma
Linguagens e Problemas
● Porém em alguns casos problemas são mais do que 
linguagens
● Ex: Dada uma string ASCII
○ Decidir se é ou não um elemento de Lc (conjunto de 
programas válidos em C)
● Mas por trás:
○ Compilador precisa fazer uma tarefa complexa
○ Produz uma árvore de análise sintática
○ Entradas em uma tabela de símbolos
○ Transformar um programa C em código-objeto
○ Outras tarefas de compiladores
○ Vai além de responder “sim” ou “não” sobre a validade de 
um programa
Linguagens e problemas
● Problemas são úteis à teoria da complexidade
○ Técnicas podem provar que alguns problemas não 
podem ser resolvidos facilmente
● O termo preferido depende do ponto de vista
○ Se estamos interessados nas palavras em si: linguagem
○ Se estamos mais interessados nas coisas que 
representam – semântica: problema
● Para a teoria computacional, estamos interessados em 
saber os limites de complexidade
○ Encontrar uma solução para a versão linguagem 
(sim/não) é tão difícil quanto a versão “resolva isso”
● É muito útil pensar em linguagens
○ Ao estudar teoria da computação
Linguagens e problemas
● Definindo linguagens
● Formador de conjuntos
○ {w | algo sobre w}
● Exs:
○ {w | w consiste em um número igual de 0’s e 1’s}
○ {w | w é um número inteiro binário primo}
○ {w | w é um programa em C sintaticamente correto}
○ {0i1j | 0 ≤ i ≤ j}
Fim
Aula 01 - Introdução
Slides/LFA.2015.2.Aula02.Aut�matos Finitos.pdf
Aula 02 - Autômatos finitos
Linguagens Formais e 
Autômatos
Prof. Dr. Daniel Lucrédio
Departamento de Computação / UFSCar
Última revisão: ago/2015
Referências bibliográficas
● Introdução à teoria dos autômatos, linguagens e computação / John 
E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman ; tradução da 2.ed. 
original de Vandenberg D. de Souza. - Rio de Janeiro : Elsevier, 2002 
(Tradução de: Introduction to automata theory, languages, and 
computation - ISBN 85-352-1072-5)
○ Capítulo 2 - Seções 2.1 e 2.2
● Introdução à teoria da computação / Michael Sipser ; tradução técnica 
Ruy José Guerra Barretto de Queiroz ; revisão técnica Newton José
Vieira. 
-- São Paulo : Thomson Learning, 2007 (Título original : Introduction to the 
theory of computation. "Tradução da segunda edição norte-americana" - 
ISBN 978-85-221-0499-4)
○ Capítulo 1 - Seção 1.1
Autômatos finitos
● Definição informal
○ Conjunto de estados: cada um “lembra” o que já foi 
feito na história de um sistema
○ Conjunto de transições: movimentos possíveis de 
um estado para outro
○ Controle: dispositivo hipotético que lê uma entrada 
externa e move de um estado para outro
○ Existem transições que não mudam o estado
○ Exemplo: geladeira
Autômatos finitos
Fechada
Aberta Alarme
AbrirFechar
10 seg
20 seg
10 seg
20 seg
Autômatos finitos
● Exercício: Locadora de vídeo
Disponível
Empréstimo
Reservado
Alugado
Atrasado
Devolução
Data 
passou
Devolução com multa
Reserva
Desistência
Empréstimo reservado
Reserva
Autômatos finitos
● Aplicações
○ Avaliar um determinado processo/protocolo em 
busca de erros/falhas
○ Ex: e se eu fechar a porta com o alarme tocando? 
○ Ex: e se eu reservar um filme atrasado?
○ Dependendo da implementação, pode resultar em 
erros
Autômatos finitos determinísticos
● Definição Formal: DFA
● A=(Q,Ʃ,δ,q0,F)
○ Q=Conjunto finito de estados
○ Ʃ=Conjunto finito de símbolos de entrada
○ δ=Função de transição
○ q0=Um estado inicial (q0 ∈ Q)
○ F=Um conjunto de estados finais ou de aceitação (F 
⊆ Q)
Autômatos finitos determinísticos
● Função de transição
○ δ:Q × Ʃ → Q
● Define o funcionamento do autômato
● Ex. da geladeira:
○ Precisa ter estado inicial e de aceitação
○ Q = {Fechada, Aberta, Alarme}
○ Ʃ = {abrir, fechar, 10seg, 20seg}
○ q0 = Fechada
○ F = {Fechada}
Autômatos finitos determinísticos
● δ(Fechada, abrir) = Aberta
● δ(Aberta, fechar) = Fechada
● δ(Aberta, 10seg) = Alarme
● δ(Alarme, 20seg) = Aberta
Autômatos finitos determinísticos
● Em um DFA
○ As transições estão completas
○ Para todo estado e todo símbolo de entrada
○ Sempre sabe o que fazer
■ Definição de determinismo
Autômatos finitos determinísticos
● Notações
○ Diagramas (Exemplo mais comum)
○ Tabelas de transição (Versão tabular do diagrama)
○ Representam completamente a 5-upla do autômato
● Diagrama de estado
○ Cada estado tem um nó correspondente
○ Estado inicial (seta apontando para o estado a partir 
do nada)
○ Estado de aceitação (círculo duplo)
○ Setas saindo de um estado para outro são 
transições
■ Representação visual da função δ
Autômatos finitos determinísticos
● Ex:{x01y | x e y são quaisquer strings de 0’s e 1’s}
q0 q1 q2
Início
1
0
0
1
0,1
Autômatos finitos determinísticos
● Versão tabular
○ Linhas correspondem aos estados
○ Colunas correspondem às entradas
○ Estado inicial é marcado com uma seta
○ Estados de aceitação são marcados com asterisco
0 1
→ q0 q1 q0
 q1 q1 q2
 * q2 q2 q2
Autômatos finitos determinísticos
● Um DFA denota uma linguagem
○ Conjunto de todas as cadeias que aceita
○ L(M) = A
○ M reconhece A
○ M aceita A
○ Mesmo que um M não aceite nenhuma cadeia
■ Ele aceita a linguagem vazia ∅
Autômatos finitos determinísticos
● Quando o autômato recebe uma cadeia de entrada
○ Processa a cadeia e produz uma saída: aceita ou rejeita
○ Começa no estado inicial
○ Lê símbolos da esquerda para a direita
○ Após ler um símbolo, move-se de um estado para outro, 
de acordo com a função de transição
○ Quando lê o último símbolo, produz a saída
○ Se o autômato estiver em estado de aceitação, a saída 
será aceita
○ Caso contrário, será rejeitada
● Ex: abrir-fechar-abrir-fechar
● Ex: 0010111
Autômatos finitos determinísticos
● Definição formal de linguagem (indutiva)
○ δ(q,a)=p
○ δˆ(q,ε)=q
○ δˆ(q,w)= δ(δˆ(q,x),a) onde w=xa
○ L(A)={w| δˆ(qo,w) está em F}
● Definição:
○ Se L é L(A) para algum DFA
○ L é regular
Autômatos finitos determinísticos
● Configuração instantânea
● w1w2w3...wkqwk+1wk+2...wn-2wn-1wn
● Ex:
○ Entrada: 001010011
○ Configuração: 001[q3]010011
○ Já leu 001, falta ler 010011
○ Encontra-se no estado q3
○ Próxima entrada é 0
Interpretando autômatos finitos
● Dado o seguinte autômato finito:
q1 q2 q3
0
1
1
0
0,1
Interpretando autômatos finitos
● Calcule a função estendida e mostre, passo a 
passo, as configurações instantâneas para as 
seguintes cadeias:
00000 0100 01000 010000 010101 11111
● Quais dessas cadeias fazem parte da linguagem do 
autômato?
● Descreva informalmente a linguagem do autômato
● Descreva formalmente a linguagem do autômato
Respostas
● Linguagens com um 1 pelo menos e um número 
par de zeros depois do último 1 (zero é par)
○ A = {w | w contém pelo menos um 1 e um número 
par de 0s segue o último 1}
Interpretando autômatos finitos
● Dado o seguinte autômato finito:
q1q0
q2 q3
1
1
00
1
1
00
Interpretando autômatos finitos
● Calcule a função estendida e mostre, passo a 
passo, as configurações instantâneas para as 
seguintes cadeias:
0101 0110 1001 1111 1 11100
● Quais dessas cadeias fazem parte da linguagem do 
autômato?
● Descreva informalmente a linguagem do autômato
● Descreva formalmente a linguagem do autômato
Respostas
● Cadeias com um número par de 0s e 1s
● L = {w | w tem ao mesmo tempo um número par de 
0s e um número par de 1s}
Interpretando Autômatos Finitos
● Dado o seguinte autômato finito:
0 1
→ q1 q1 q2
 * q2 q1 q2
Interpretando autômatos finitos
● Calcule a função estendida e mostre, passo a 
passo, as configurações instantâneas para as 
seguintes cadeias:
○ 010 0111110 0000001 1101 001 11100
● Quais dessas cadeias fazem parte da linguagem do 
autômato?
● Descreva informalmente a linguagem do autômato
● Descreva formalmente a linguagem do autômato
Respostas
● Todas as cadeias que terminam com 1
● L = {w | w termina com um 1}
Interpretando autômatos finitos
s
q1
a
q2
a
b a
b
r1
b
r2
a b
a
b
Interpretando autômatos finitos
● Calcule a função estendida e mostre, passo a passo, as 
configurações instantâneas para as seguintes cadeias:
a b aa bb bab ab ba bbba
● Quais dessas cadeias fazem parte da linguagem do 
autômato?
● Descreva informalmente a linguagem do autômato
● Descreva formalmente a linguagem do autômato
Respostas
● Cadeias que começam e terminam com o mesmo 
símbolo
● L = {w | w começa e termina com a ou w começa e 
termina com b}
Projetando autômatos finitos
● Projetar é um processo criativo
● Não pode ser reduzido a uma receita ou fórmula 
simples
● Dica: ponha-se a si próprio no lugar da máquina 
que está tentando projetar
○ Veja como você se conduziria para realizar a tarefa 
da máquina
○ Você recebe uma cadeia de entrada
○ Vai vendo os símbolos um por um
○ Você não sabe quando o final da cadeia está vindo
○ Tem que estar sempre pronto com a resposta
Projetando autômatos finitos
● Você precisa lembrar coisas sobre a cadeia
○ Impossível lembrar tudo
○ Autômatos finitos não sabem contar!
○ Nem você consegue lembrar tudo
■ Imagine uma entrada com 1000 dígitos
○ Precisa ter uma lógica
○ Um raciocínio
■ Essa informação é crucial
■ Depende do feeling, talento, dom, etc...
Projetando
autômatos finitos
● Ex: 
○ Ʃ = {0,1}
○ Linguagem = cadeias com número ímpar de 1s
qÍmparqPar
1
1
0 0
Projetando autômatos finitos
● Ex:
○ Ʃ = {0,1}
○ Linguagem = cadeias que contém a cadeia 001 
como uma subcadeia
q q0 q00 q001
1
0
1
0 1
0
0,1
Projetando autômatos finitos
● Ex:
○ Ʃ = {0,1}
○ Linguagem = cadeias que terminam em 00
q q0 q00
1
0
1
0
0
1
Mais um exercício
● Linguagem A consistindo de todas as cadeias 
sobre {0,1} contendo um 1 na terceira posição a 
partir do final
○ Ex: 000100, 010110 estão em A, mas 0011 não
Mais um exercício
Fim
Aula 02 - Autômatos finitos
Slides/LFA.2015.2.Aula03.Minimiza��o de DFAs.pdf
Linguagens Formais e 
Autômatos
Aula 03 - Minimização de DFAs
Prof. Dr. Daniel Lucrédio
Departamento de Computação / UFSCar
Última revisão: ago/2015
Referências bibliográficas
● Introdução à teoria dos autômatos, linguagens e computação / John 
E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman ; tradução da 2.ed. 
original de Vandenberg D. de Souza. - Rio de Janeiro : Elsevier, 2002 
(Tradução de: Introduction to automata theory, languages, and 
computation - ISBN 85-352-1072-5)
○ Capítulo 4 - Seção 4.4
Minimização de DFAs
● Existe um procedimento que minimiza um DFA
○ Ou seja, dado um DFA, ele permite encontrar um 
DFA equivalente que tenha o número mínimo de 
estados.
● De fato, esse DFA é mínimo:
○ Teorema: Se A é um DFA e M é o DFA construído a 
partir de A pelo algoritmo descrito a seguir, então M 
tem tão poucos estados quanto qualquer DFA 
equivalente a A
○ Em outras palavras, podemos testar a equivalência 
entre DFAs
■ Minimizando os dois e verificando se são iguais (com 
exceção, possivelmente, dos nomes dos estados)
Minimização de DFAs
● Conceito de estados equivalentes
○ Objetivo: entender quando dois estados distintos p e 
q podem ser substituídos por um único estado que 
se comporte como p e q
● Formalmente:
○ Dois estados p e q são equivalentes se:
■ Para todas as cadeias de entrada w, δ^(p, w) é um estado 
de aceitação se e somente se δ^(q, w) é um estado de 
aceitação
Minimização de DFAs
● Menos formalmente:
○ Existe uma cadeia w que leva p à aceitação e w à 
não-aceitação (ou vice-versa)?
○ Se existir pelo menos uma cadeia assim, os estados 
são distinguíveis
■ Caso contrário, são equivalentes!
Minimização de DFAs
● Ilustrando:
○ 0,1, 010, 111 não distingue p e q
○ 11 distingue p e q
○ r e s são distinguíveis (ε os distingue)
p
q
r
s
0,1
0,1
1
0,1
1
1
1
0
0
0
0
0,1
Minimização de DFAs
● Difícil encontrar estados equivalentes apenas 
“olhando” para o DFA
○ Muitas combinações, fácil se perder
● Estratégia sistemática: encontrar todos os pares de 
estados que sejam distinguíveis
○ Se fizermos o melhor possível
■ Qualquer par de estados que não considerarmos 
distinguíveis serão equivalentes
● Algoritmo de preenchimento de tabela
○ Descoberta recursiva de pares distinguíveis
○ Cada célula da tabela marca um par distinguível
○ Células em branco marcam pares equivalentes
A B C D E F G
B
C
D
E
F
G
H
x x
x
x
x
x
x
A B C D E F G
B
C
D
E
F
G
H
Começamos pelos estados de aceitação/não-
aceitação. São obviamente pares distinguíveis 
pela cadeia vazia
x x
x
x
x
x
x
A B C D E F G
B
C
D
E
F
G
H
Agora tentamos encontrar outros estados que 
“chegam” em um par conhecido, dada uma 
mesma entrada.
A técnica é seguir, para cada par distinguível, as 
setas pelo lado inverso, com um mesmo rótulo
Fica mais fácil se marcar as células já analisadas
x x
x
x
x
x
x
A B C D E F G
B
C
D
E
F
G
H
Exs: 
(a) Seguindo as setas que “chegam” em A e C (um par 
distinguível), mediante entrada 0, temos:
● SetasA_0:{C}, SetasC_0:{D,F}
● Novos pares = SetasA_0 x SetasC_0 = {(C,D), (C,F)}
● Estes pares já estão marcados na tabela, com um x
● Analisando para entrada 1, temos:
● SetasA_1: {}, SetasC_1: {B,C,H}
● Novos pares = SetasA_1 X SetasC_1 = {} (nenhum novo par)
● Uma vez que já analisamos as entradas 0 e 1, a célula (A,C) 
foi analisada e é marcada
x
x
x
x
x
x
x
x
x
A B C D E F G
B
C
D
E
F
G
H
Exs: 
(b) Continuando para par (B,C):
● SetasB_0:{A}, SetasC_0:{D,F}
● Novos pares = SetasB_0 x SetasC_0 = {(A,D), (A,F)}
● Esses pares ainda não foram marcados, e portanto a tabela 
precisa ser atualizada
● SetasB_1: {}, SetasC_1: {B,C,H}
● Novos pares = SetasB_1 X SetasC_1 = {} (nenhum novo par)
● Uma vez que já analisamos as entradas 0 e 1, a célula (B,C) 
foi analisada e é marcada
x
x
x
x
x
x
x
x
x
A B C D E F G
B
C
D
E
F
G
H
Exs: 
(c) Continuando para par (C,D):
● SetasC_0:{D,F}, SetasD_0:{}
● Novos pares = {}
● SetasC_1:{B,C,H}, SetasD_1: {}
● Novos pares = {}
● Nenhum novo par
x
x
x
x
x
x
x
x
x
x x
A B C D E F G
B
C
D
E
F
G
H
Exs: 
(d) Continuando para par (C,E):
● SetasC_0:{D,F}, SetasE_0:{}
● Novos pares = {}
● SetasC_1:{B,C,H}, SetasE_1: {G}
● Novos pares = {(B,G),(C,G),(H,G)}
● Novos pares e a célula (C,E) são marcados
x
x
x
x
x
x
x
x
x
x
x
x
x x x
A B C D E F G
B
C
D
E
F
G
H
Exs: 
(e) Continuando para par (C,F):
● SetasC_0:{D,F}, SetasF_0:{}
● Novos pares = {}
● SetasC_1:{B,C,H}, SetasF_1: {A,E}
● Novos pares = {(B,A),(B,E),(C,A),(C,E),(H,A),(H,E)}
● Novos pares e a célula (C,F) são marcados
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x x
x
x x
A B C D E F G
B
C
D
E
F
G
H
Exs: 
(f) Continuando para par (C,G):
● SetasC_0:{D,F}, SetasG_0:{B,G,H}
● Novos pares = {(D,B),(D,G),(D,H),(F,B),(F,G),(F,H)}
● SetasC_1:{B,C,H}, SetasG_1: {D,F}
● Novos pares = {(B,D),(B,F),(C,D),(C,F),(H,D),(H,F)}
● Novos pares e a célula (C,G) são marcados
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x x
A B C D E F G
B
C
D
E
F
G
H
Exs: 
(g) Continuando para par (C,H):
● SetasC_0:{D,F}, SetasH_0:{E}
● Novos pares = {(D,E),(F,E)}
● SetasC_1:{B,C,H}, SetasH_1: {}
● Novos pares = {}
● Novos pares e a célula (C,H) são marcados
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x x
A B C D E F G
B
C
D
E
F
G
H
Exs: 
(h) Continuando para par (A,B):
● SetasA_0:{C}, SetasB_0:{A}
● Novos pares = {(A,C)}
● SetasA_1:{}, SetasB_1: {}
● Novos pares = {}
● Novos pares e a célula (A,B) são marcados
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x x
A B C D E F G
B
C
D
E
F
G
H
Exs: 
(h) Continuando para par (A,D):
● SetasA_0:{C}, SetasD_0:{}
● Novos pares = {(A,C)}
● SetasA_1:{}, SetasD_1: {}
● Novos pares = {}
● Célula (A,D) é marcada
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x x
A B C D E F G
B
C
D
E
F
G
H
Exs: 
(h) Continuando para par (A,F):
● SetasA_0:{C}, SetasF_0:{}
● Novos pares = {(A,C)}
● SetasA_1:{}, SetasF_1: {A,E}
● Novos pares = {}
● Célula (A,F) é marcada
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x x
A B C D E F G
B
C
D
E
F
G
H
Exs: 
(h) Continuando para par (A,H):
● SetasA_0:{C}, SetasH_0:{E}
● Novos
pares = {(C,E)}
● SetasA_1:{}, SetasH_1: {}
● Novos pares = {}
● Célula (A,H) é marcada
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x x
A B C D E F G
B
C
D
E
F
G
H
Exs: 
(i) Continuando para par (B,D):
● SetasB_0:{A}, SetasD_0:{}
● Novos pares = {}
● SetasB_1:{}, SetasD_1: {}
● Novos pares = {}
● Célula (B,D) é marcada
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x x
A B C D E F G
B
C
D
E
F
G
H
Exs: 
(i) Continuando para par (B,E):
● SetasB_0:{A}, SetasE_0:{}
● Novos pares = {}
● SetasB_1:{}, SetasE_1: {G}
● Novos pares = {}
● Célula (B,E) é marcada
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x x
A B C D E F G
B
C
D
E
F
G
H
Exs: 
(j) Continuando para par (B,F):
● SetasB_0:{A}, SetasF_0:{}
● Novos pares = {}
● SetasB_1:{}, SetasF_1: {A,E}
● Novos pares = {}
● Célula (B,F) é marcada
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x x
A B C D E F G
B
C
D
E
F
G
H
Exs: 
(k) Continuando para par (B,G):
● SetasB_0:{A}, SetasG_0:{B,G,H}
● Novos pares = {(A,B),(A,G),(A,H)}
● SetasB_1:{}, SetasG_1: {D,F}
● Novos pares = {}
● Novo par e célula (B,G) são marcados
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x x
A B C D E F G
B
C
D
E
F
G
H
Exs: 
(l) Continuando para par (A,G):
● SetasA_0:{C}, SetasG_0:{B,G,H}
● Novos pares = {(C,B),(C,G),(C,H)}
● SetasA_1:{}, SetasG_1: {D,F}
● Novos pares = {}
● Célula (A,G) é marcada
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x x
A B C D E F G
B
C
D
E
F
G
H
Exs: 
(m) Continuando para par (D,E):
● SetasD_0:{}, SetasE_0:{}
● Novos pares = {}
● SetasD_1:{}, SetasE_1: {G}
● Novos pares = {}
● Células (D,E), (D,G) e (D,H) são marcadas (pois SetasD_0 e 
SetasD_1 são vazios)
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x x
A B C D E F G
B
C
D
E
F
G
H
Exs: 
(n) Continuando para par (E,F):
● SetasE_0:{}, SetasF_0:{}
● Novos pares = {}
● SetasE_1:{G}, SetasF_1: {A,G}
● Novos pares = {(A,G)}
● Célula (E,F) é marcada
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x x
A B C D E F G
B
C
D
E
F
G
H
Exs: 
(o) Continuando para par (E,H):
● SetasE_0:{}, SetasH_0:{E}
● Novos pares = {}
● SetasE_1:{G}, SetasH_1: {}
● Novos pares = {}
● Célula (E,H) é marcada
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x x
A B C D E F G
B
C
D
E
F
G
H
Exs: 
(p) Continuando para par (F,G):
● SetasF_0:{}, SetasG_0:{B,G,H}
● Novos pares = {}
● SetasF_1:{A,E}, SetasG_1: {D,F}
● Novos pares = {(A,D),(A,F),(E,D),(E,F)}
● Célula (F,G) é marcada
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x x
A B C D E F G
B
C
D
E
F
G
H
Exs: 
(q) Continuando para par (F,H):
● SetasF_0:{}, SetasH_0:{E}
● Novos pares = {}
● SetasF_1:{A,E}, SetasH_1: {}
● Novos pares = {}
● Célula (F,H) é marcada
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x x
A B C D E F G
B
C
D
E
F
G
H
Exs: 
(q) Continuando para par (G,H):
● SetasG_0:{B,G,H}, SetasH_0:{E}
● Novos pares = {(B,E),(G,E),(H,E)}
● SetasG_1:{D,F}, SetasH_1: {}
● Novos pares = {}
● Novo par e célula (G,H) são marcados
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x x
A B C D E F G
B
C
D
E
F
G
H
Exs: 
(r) Continuando para par (G,E):
● SetasG_0:{B,G,H}, SetasE_0:{}
● Novos pares = {}
● SetasG_1:{D,F}, SetasE_1: {G}
● Novos pares = {(D,G),(F,G)}
● Célula (G,E) é marcada
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x x
A B C D E F G
B
C
D
E
F
G
H
Resultado:
- São pares equivalentes: (A,E), (B,
H) e (D,F)
Minimização de DFAs
● Algoritmo em duas etapas:
○ a. Eliminar estados inalcançáveis
■ Reduz o trabalho do algoritmo de preenchimento de tabela
○ b. Particionar os estados restantes em blocos de 
estados equivalentes
■ Primeiro deve-se identificar os pares equivalentes
■ Depois formar os grupos de estados equivalentes
Estados inalcançáveis
Estados alcançáveis 
devem ter um caminho 
a partir do estado 
inicial
Neste exemplo, o 
estado D é 
inalcançável
Particionamento em grupos de 
estados equivalentes
Neste exemplo, são pares equivalentes: (A,E), (B,H) e (D,F)
- Partição: {A,E},{B,H},{D,F},{C},{G}
Importante: deve-se considerar o caráter transitivo da equivalência. Por 
exemplo, se os pares equivalentes fossem: (A,E), (E,H), (D,F)
- A partição seria: {A,E,H},{D,F},{B},{C},{G}
(Ou seja, A é equivalente a E, E é equivalente a H, portanto A é 
equivalente a H, e os três formam um único grupo)
Particionamento em grupos de 
estados equivalentes
0 1
{A,E} {B,H} {F}
{B,H} {G} {C}
{D,F} {C} {G}
{C} {A} {C}
{G} {G} {E}
Para concluir a minimização, 
basta definir a nova função de 
transição
Para isso, monta-se uma 
tabela vazia, onde cada estado 
é um grupo da partição
As transições são definidas 
como a união das transições 
no autômato original
Particionamento em grupos de 
estados equivalentes
0 1
{A,E} {B,H} {D,F}
{B,H} {G} {C}
{D,F} {C} {G}
{C} {A,E} {C}
{G} {G} {A,E}
Agora, basta substituir os valores 
das células por grupos que 
representam estados válidos (a 
primeira coluna da tabela)
De {F} 
para {D,
F}
De {A} 
para {A,
E}
0 1
{A,E} {B,H} {F}
{B,H} {G} {C}
{D,F} {C} {G}
{C} {A} {C}
{G} {G} {E} De {E} 
para {A,
E}
Nunca haverá conflito, devido ao 
algoritmo de preenchimento da 
tabela
Particionamento em grupos de 
estados equivalentes
0 1
→ {A,E} {B,H} {D,F}
{B,H} {G} {C}
{D,F} {C} {G}
* {C} {A,E} {C}
{G} {G} {A,E}
Para concluir, renomeie 
os estados para ficar 
mais legível
0 1
→ Q1 Q2 Q3
Q2 Q5 Q4
Q3 Q4 Q5
* Q4 Q1 Q4
Q5 Q5 Q1
Estados iniciais e de 
aceitação são os grupos 
que contém os estados 
iniciais e de aceitação do 
DFA original
Fim
Aula 03 - Minimização de DFAs
Slides/LFA.2015.2.Aula04.N�o Determinismo.pdf
Aula 04 - Não determinismo
Linguagens Formais e 
Autômatos
Prof. Dr. Daniel Lucrédio
Departamento de Computação / UFSCar
Última revisão: ago/2015
Referências bibliográficas
● Introdução à teoria dos autômatos, linguagens e computação / John 
E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman ; tradução da 2.ed. 
original de Vandenberg D. de Souza. - Rio de Janeiro : Elsevier, 2002 
(Tradução de: Introduction to automata theory, languages, and 
computation - ISBN 85-352-1072-5)
○ Capítulo 2 - Seção 2.3
● Introdução à teoria da computação / Michael Sipser ; tradução técnica 
Ruy José Guerra Barretto de Queiroz ; revisão técnica Newton José Vieira. 
-- São Paulo : Thomson Learning, 2007 (Título original : Introduction to the 
theory of computation. "Tradução da segunda edição norte-americana" - 
ISBN 978-85-221-0499-4)
○ Capítulo 1 - Seção 1.2
Mais um exercício
● Linguagem A consistindo de todas as cadeias 
sobre {0,1} contendo um 1 na terceira posição
a 
partir do final
○ Ex: 000100, 010110 estão em A, mas 0011 não
Mais um exercício
Não-Determinismo
● Determinismo é como achar um caminho com um 
GPS
○ Ele avisa a cada esquina
○ Não há dúvida
● Não-determinismo exige “adivinhação”
○ Não é possível saber todos os passos
Não-Determinismo
● Um autômato pode estar em muitos estados ao 
mesmo tempo
○ No diagrama:
■ DFA tem exatamente 1 seta com 1 símbolo para todo 
símbolo e estado
■ NFA pode ter zero ou mais setas para um símbolo/estado
○ Na tabela
■ DFA é completamente preenchida, com exatamente um 
estado em cada célula
■ NFA pode ter células com zero ou mais estados
Não-Determinismo
● O que isto significa na prática?
○ Uma visão: um NFA pode “adivinhar” algumas 
coisas sobre a entrada (poder paranormal)
○ Outra visão: em transições para mais de um estado, 
é o mesmo que dividir o autômato em dois e seguir 
cada execução em paralelo
○ Outra: uma árvore de possibilidades – tentativa e 
erro
Não-Determinismo
● Mais fáceis de projetar e entender
○ Ex: Ʃ = {0,1}
○ A é uma linguagem consistindo de todas as cadeias 
contendo um 1 na terceira posição a partir do final 
(exemplo: 000100)
Não-Determinismo
● Ex: Ʃ = {0,1}
● A é uma linguagem que 
aceita cadeias da forma 
0k, onde k é um múltiplo 
de 2 ou 3
Autômatos finitos não-
determinísticos
● Definição formal: NFA
● A=(Q,Ʃ,δ,q0,F)
○ Q=Conjunto finito de estados
○ Ʃ=Conjunto finito de símbolos de entrada
○ δ=Função de transição
○ q0=Um estado inicial (q0 ∈ Q)
○ F=Um conjunto de estados finais ou de aceitação (F 
⊆ Q)
● Diferença está na função de transição
○ δ:Q × Ʃ → Q*
Autômatos finitos determinísticos
● RELEMBRANDO os AFD:
● Definição formal de linguagem (indutiva)
○ δ(q,a)=p
○ δ^(q,ε)=q
○ δ^(q,w)= δ(δ^(q,x),a) onde w=xa
○ L(A)={w| δ^(qo,w) está em F}
● Definição:
○ Se L é L(A) para algum DFA
○ L é regular
Autômatos finitos não-
determinísticos
● Definição formal de linguagem
○ δ^(q,ε)={q}
○ δ^(q,x)= {p1,p2,...,pk}
○ δ^(q,w)=união de todos δ(pi,a), onde w=xa
○ L(A)={w| δ^(qo,w) ∩ F ≠ ∅}
● Definição:
○ Se L é L(A) para algum NFA
○ L é regular
Interpretando NFAs
Interpretando NFAs
● Calcule a função estendida e mostre, passo a 
passo, as configurações instantâneas para as 
seguintes cadeias:
○ 111
○ 010
○ 0100
○ (Use notação de árvore ou conjuntos)
● Descreva a linguagem reconhecida por este 
autômato
Interpretando NFAs
Ʃ = {1,2,3,4}
Interpretando NFAs
● Calcule a função estendida e mostre, passo a 
passo, as configurações instantâneas para as 
seguintes cadeias:
○ 1234
○ 123
○ 1231
○ 433
○ 412
○ (Use notação de árvore ou conjuntos)
● Descreva a linguagem reconhecida por este 
autômato
Interpretando NFAs
● Resposta
○ Aceita cadeias cujo símbolo final já apareceu antes
Interpretando NFAs
Interpretando NFAs
● Calcule a função estendida e mostre, passo a 
passo, as configurações instantâneas para as 
seguintes cadeias:
○ ave
○ avião
○ aves
○ chave
○ (Use notação de árvore ou conjuntos)
● Descreva a linguagem reconhecida por este 
autômato
Interpretando NFAs
● Dado o seguinte autômato finito:
0 1
 → q0 {q0,q1} {q0}
 q1 ∅ {q2}
 * q2 ∅ ∅
Interpretando NFAs
● Calcule a função estendida e mostre, passo a 
passo, as configurações instantâneas para as 
seguintes cadeias:
○ 0101010
○ 11111
○ 001
○ 1101
○ (Use notação de árvore ou conjuntos)
● Descreva a linguagem aceita por este autômato
○ Resp: cadeias que terminam em 01
Projetando NFAs
● Ex:
○ Ʃ = {a,b,c,...,z}
○ Linguagem = cadeias que contém a cadeia “pre” 
como uma subcadeia
Projetando NFAs
● Ex:
○ Ʃ = {0,1}
○ Linguagem = cadeias que não possuem símbolos 
repetidos em sequência
Fim
Aula 04 - Não-determinismo
Slides/LFA.2015.2.Aula05.Equival�ncia DFA x NFA.pdf
Aula 05 - Equivalência DFA x NFA
Linguagens Formais e 
Autômatos
Prof. Dr. Daniel Lucrédio
Departamento de Computação / UFSCar
Última revisão: ago/2015
Referências bibliográficas
● Introdução à teoria dos autômatos, linguagens e computação / John 
E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman ; tradução da 2.ed. 
original de Vandenberg D. de Souza. - Rio de Janeiro : Elsevier, 2002 
(Tradução de: Introduction to automata theory, languages, and 
computation - ISBN 85-352-1072-5)
○ Capítulo 2 - Seção 2.3
● Introdução à teoria da computação / Michael Sipser ; tradução técnica 
Ruy José Guerra Barretto de Queiroz ; revisão técnica Newton José Vieira. 
-- São Paulo : Thomson Learning, 2007 (Título original : Introduction to the 
theory of computation. "Tradução da segunda edição norte-americana" - 
ISBN 978-85-221-0499-4)
○ Capítulo 1 - Seção 1.2
Equivalência DFA e NFA
● Intuitivamente, NFA é mais poderoso
○ Mas as linguagens aceitas por um NFA são 
regulares
○ Ou seja, qualquer NFA pode ser convertido em um 
DFA que reconhece a mesma linguagem
● Teorema:
○ Uma Linguagem L é aceita por algum DFA se e 
somente se L é aceita por algum NFA
○ Prova por construção dos dois lados:
■ “Se”: um processo que constrói um DFA a partir de um 
NFA
■ “Somente se”: um processo que constrói um NFA a partir 
de um DFA
Conversão NFA → DFA
● Na maioria dos casos, um DFA equivalente tem o 
mesmo número de estados que o NFA, só que mais 
transições
● No pior caso, tem 2n estados
○ NFA N = (QN, Ʃ, δN, q0, FN)
○ DFA D = (QD, Ʃ, δD, {q0}, FD)
○ L(D) = L(N)
● QD é o conjunto de subconjuntos de QN
● FD é o conjunto S de subconjuntos de QN,
tal que S ∩ FN ≠ ∅
● Para cada conjunto S ⊆ QN
○ e para cada a ∈ Ʃ
○ δD(S,a) = ∪ todos os δN(p,a) para p ∈ S
Conversão NFA → DFA
● Consiste em pegar todas as combinações de 
estados e agregar as transições do NFA
○ Cada combinação de estados do NFA é um estado 
no DFA
● Consiste basicamente na implementação “em 
paralelo”
○ Mas pré-calculando as combinações de estados
Conversão NFA → DFA
● Passo a passo com exemplo
● Dado o NFA (cadeias que terminam com 01):
0 1
 → q0 {q0,q1} {q0}
 q1 ∅ {q2}
 * q2 ∅ ∅
Conversão NFA → DFA
● Passo 1:
○ Faça uma tabela “vazia”, com as mesmas entradas 
como colunas (a tabela vai crescer para baixo)
0 1
 
 
Conversão NFA → DFA
● Passo 2:
○ Crie um novo estado inicial no DFA, um conjunto 
que contém somente o estado inicial do NFA
0 1
→ {q0}
 
Conversão NFA → DFA
● Passo 3:
○ Para cada entrada, insira no DFA um conjunto que 
contém a união de todos os resultados da transição 
NFA daquela entrada para todos os estados do 
conjunto à esquerda
0 1
→ {q0} {q0,q1} {q0}
 
Conversão NFA → DFA
● Passo 4:
○ Para cada novo conjunto de estados que aparecer, 
insira uma nova linha na tabela do DFA e volte para 
o passo 3
0 1
→ {q0} {q0,q1} {q0}
 {q0,q1} {q0,q1} {q0,q2}
Conversão NFA → DFA
● Passo 4 (novamente):
0 1
→ {q0} {q0,q1} {q0}
 {q0,q1} {q0,q1} {q0,q2}
 {q0,q2} {q0,q1} {q0}
Conversão NFA → DFA
● Passo 5: Quando não houver mais novos estados, 
marque como estado de aceitação os conjuntos 
que contém ao menos um estado de aceitação do 
NFA
0 1
→ {q0} {q0,q1} {q0}
 {q0,q1} {q0,q1} {q0,q2}
 * {q0,q2} {q0,q1} {q0}
Conversão NFA → DFA
● Passo 6: “Renomeie” os conjuntos para estados, de 
forma
a facilitar a leitura do DFA
0 1
→ A B A
 B B C
 * C B A
Conversão NFA → DFA
● Dado o seguinte NFA:
○ Construa um DFA que aceite a mesma linguagem
0 1
 → p {p,q} {p}
 q {r} {r}
 r {s} ∅
 * s {s} {s}
Conversão NFA → DFA
0 1
→ {p} A {p,q} B {p} A
 {p,q} B {p,q,r} D {p,r} C
 {p,r} C {p,q,s} E {p} A
 {p,q,r} D {p,q,r,s} F {p,r} C
 * {p,q,s} E {p,q,r,s} F {p,r,s} G
 * {p,q,r,s} F {p,q,r,s} F {p,r,s} G
 * {p,r,s} G {p,q,s} E {p,s} H
 * {p,s} H {p,q,s} E {p,s} H
Conversão NFA → DFA
● Dado o seguinte NFA:
○ Construa um DFA que aceite a mesma linguagem
0 1
 → * q0 {q1} {q2}
 * q1 ∅ {q0}
 * q2 {q0} ∅
Conversão NFA → DFA
0 1
→ * {q0} A {q1} B {q2} C
 * {q1} B {} D {q0} A
 * {q2} C {q0} A {} D
 {} D (morto) {} D {} D
Conversão DFA → NFA
● “Resto” da prova
● Parte fácil
○ Construir um NFA a partir de um DFA
○ Basta “copiar” o diagrama (ou tabela), trocando 
estados por conjuntos de estados
○ Um DFA é um caso específico de NFA
■ NFA permite 0 ou mais transições em cada situação
■ DFA permite sempre 1 transição em cada situação
■ 1 está entre 0 ou mais
Conversão DFA → NFA
0 1
→ q1 q1 q2
 * q2 q1 q2
0 1
→ q1 {q1} {q2}
 * q2 {q1} {q2}
Conversão DFA → NFA
● Formalmente:
○ Seja D = (Q,Ʃ,δD,q0,F) um DFA
○ Defina N = (Q,Ʃ,δN,q0,F)
■ Onde δN é definido pela regra:
● Se δD(q,a)=p, então δN(q,a)={p}
● Como consequência
○ Se δ^D(q0,w)=p, então δ^N(q0,w)={p}
● Portanto, w é aceito por D se e somente se é aceito 
por N
○ Isto é: L(D) = L(N)
Fim
Aula 05 - Equivalência DFA x NFA
Slides/LFA.2015.2.Aula06.NFA com transi��es vazias.pdf
Aula 06 - NFA com transições vazias
Linguagens Formais e 
Autômatos
Prof. Dr. Daniel Lucrédio
Departamento de Computação / UFSCar
Última revisão: ago/2015
Referências bibliográficas
● Introdução à teoria dos autômatos, linguagens e computação / John 
E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman ; tradução da 2.ed. 
original de Vandenberg D. de Souza. - Rio de Janeiro : Elsevier, 2002 
(Tradução de: Introduction to automata theory, languages, and 
computation - ISBN 85-352-1072-5)
○ Capítulo 2 - Seção 2.5
● Introdução à teoria da computação / Michael Sipser ; tradução técnica 
Ruy José Guerra Barretto de Queiroz ; revisão técnica Newton José Vieira. 
-- São Paulo : Thomson Learning, 2007 (Título original : Introduction to the 
theory of computation. "Tradução da segunda edição norte-americana" - 
ISBN 978-85-221-0499-4)
○ Capítulo 1 - Seção 1.2
NFA com transições vazias
● Transições espontâneas
○ Isto é, sem nenhuma entrada
● É uma forma de não-determinismo
○ Facilita a “programação”
● Ex: números decimais
NFA com transições vazias
● Ex: busca por palavras-chave
NFA com transições vazias
● Definição formal
○ A mesma que NFA
○ Muda somente a função de transição
■ δ:Q × Ʃ ∪ {ε} → Q*
○ Uma coluna extra na tabela, ou transições vazias no 
diagrama
ε +,- . 0,1,...,9
→ q0 {q1} {q1} ∅ ∅
 q1 ∅ ∅ {q2} {q1,q4}
 q2 ∅ ∅ ∅ {q3}
 q3 {q5} ∅ ∅ {q3}
 q4 ∅ ∅ {q3} ∅
 * q5 ∅ ∅ ∅ ∅
NFA com transições vazias
● Essa nova característica não aumenta o poder do 
NFA
○ Ainda reconhece linguagens regulares
● Conceito de épsilon-fechamento
○ ECLOSE(q)
○ Conjunto de todos os estados alcançáveis 
espontaneamente a partir de q
■ Incluindo os vizinhos diretos e indiretos
■ Analisando-se os arcos rotulados com ε
● Função de transição estendida
○ Deve considerar sempre o ECLOSE
Interpretando ε-NFAs 
● Dado o seguinte autômato (que reconhece 
números decimais)
Interpretando ε-NFAs
● Calcule a função estendida e mostre, passo a 
passo, as configurações instantâneas para a 
seguinte cadeia:
○ 5.6
○ 67.1.2
○ (Use notação de árvore ou conjuntos)
● Passo 1: calcule ECLOSE(q0)
● Passos seguintes: mesmo que NFA
○ Porém, para cada estado alcançado, inclua o seu 
ECLOSE também
Interpretando ε-NFAs
● Resposta:
○ {q0,q1}5.6
○ 5{q1,q4}.6
○ 5.{q2,q3,q5}6
○ 5.6{q3,q5}
● Conjunto de estados finais contém q5, portanto o 
autômato aceita a cadeia
Interpretando ε-NFAs
● Dado o seguinte autômato
Interpretando ε-NFAs
● Calcule a função estendida e mostre, passo a 
passo, as configurações instantâneas para as 
seguintes cadeias:
○ ε
○ a
○ baba
○ baa
○ b
○ bb
○ babba
○ (Use notação de árvore ou conjuntos)
Interpretando ε-NFAs
● Dado o seguinte autômato
Interpretando ε-NFAs
● Calcule a função estendida e mostre, passo a 
passo, as configurações instantâneas para as 
seguintes cadeias:
○ 1111
○ 11
○ 101
○ 00010
○ (Use notação de árvore ou conjuntos)
Projetando ε-NFAs
● Ex:
○ Ʃ = {0,1}
○ Linguagem = cadeias que contém a sequência 010 
ou 101 como subcadeia
Projetando ε-NFAs
● Ex:
○ Ʃ = {a,b,c}
○ Linguagem = cadeias onde b e c sempre aparecem 
depois de uma ocorrência de a
Equivalência ε-NFAs e DFAs
● Transições vazias não adicionam poder ao 
autômato
○ Ainda reconhece as mesmas linguagens
○ Linguagens regulares
● Teorema:
○ Uma Linguagem L é aceita por algum DFA se e 
somente se L é aceita por algum ε-NFA
○ Prova por construção dos dois lados:
■ “Se”: um processo que constrói um DFA a partir de um ε-
NFA
■ “Somente se”: um processo que constrói um ε-NFA a partir 
de um DFA
Conversão ε-NFA → DFA
● É o mesmo procedimento da construção de 
subconjuntos dado anteriormente
○ Porém incorporando o cálculo de ε-fechamento após 
cada passo
○ Similar à implementação do ε-NFA
Conversão ε-NFA → DFA
● Passo a passo com exemplo
● Dado o NFA:
ε a b c
→ p ∅ {p} {q} {r}
 q {p} {q} {r} ∅
 * r {q} {r} ∅ {p}
Conversão ε-NFA → DFA
● Passo 1 (auxiliar): calcule o ECLOSE de todos os 
estados
● ECLOSE(p) = {p}
● ECLOSE(q) = {p,q}
● ECLOSE(r) = {p,q,r}
ε a b c
→ p ∅ {p} {q} {r}
 q {p} {q} {r} ∅
 * r {q} {r} ∅ {p}
Conversão ε-NFA → DFA
● Passo 2: faça uma tabela “vazia” com as entradas 
(sem a coluna ε)
a b c
 
Conversão ε-NFA → DFA
● Passo 3: Crie um novo estado inicial no DFA, um 
conjunto que contém o ECLOSE do estado inicial do 
NFA
a b c
 → {p}
Conversão ε-NFA → DFA
● Passo 4:
○ Para cada entrada, insira no DFA um conjunto que 
contém o ECLOSE da união de todos os resultados da 
transição NFA daquela entrada para todos os estados do 
conjunto à esquerda
a b c
 → {p} {p} {p,q} {p,q,r}
Conversão ε-NFA → DFA
● Passo 5:
○ Para cada novo conjunto de estados que aparecer, 
insira uma nova linha na tabela do DFA e volte para 
o passo 4
a b c
 → {p} {p} {p,q} {p,q,r}
 {p,q} {p,q} {p,q,r} {p,q,r}
 {p,q,r} {p,q,r} {p,q,r} {p,q,r}
Conversão ε-NFA → DFA
● Passo 6: Quando não houver mais novos estados, 
marque como estado de aceitação os conjuntos 
que contém ao menos um estado de aceitação do 
NFA
a b c
 → {p} {p} {p,q} {p,q,r}
 {p,q} {p,q} {p,q,r} {p,q,r}
 * {p,q,r} {p,q,r} {p,q,r} {p,q,r}
Conversão ε-NFA → DFA
● Passo 7: “Renomeie” os conjuntos para estados, de 
forma a facilitar a leitura do DFA
a b c
 → A A B C
 B B C C
 * C C C C
Conversão ε-NFA → DFA
● Dado o seguinte ε-NFA
○ Converta para um DFA que
aceita a mesma 
linguagem
ε a b c
 → p {q,r} ∅ {q} {r}
 q ∅ {p} {r} {p,q}
 * r ∅ ∅ ∅ ∅
Conversão ε-NFA → DFA
● Resposta
a b c
 → * {p,q,r} {p,q,r} {q,r} {p,q,r}
 * {q,r} {p,q,r} {r} {p,q,r}
 * {r} {} {} {}
{} {} {} {}
Conversão ε-NFA → DFA
● Dado o seguinte ε-NFA
○ Converta para um DFA que aceita a mesma 
linguagem
ε a b
 → * 1 {3} ∅ {2}
 2 ∅ {2,3} {3}
 3 ∅ {1} ∅
Conversão ε-NFA → DFA
● Resposta
a b
 → * {1,3} {1,3} {2}
 {2} {2,3} {3}
 {2,3} {1,2,3} {3}
 {3} {1,3} {}
 * {1,2,3} {1,2,3} {2,3}
 {} {} {}
Conversão DFA → ε-NFA
● “Resto” da prova
● Parte fácil
○ Mesmo caso da conversão de DFA para NFA
○ Mas fazendo com que δ(q, ε) = ∅ para todo estado q 
do DFA
○ Ou seja, não existem transições espontâneas (mas 
poderia ter)
Resumo
● Definições X Linguagens X Problemas
● Autômatos Finitos
○ DFA
○ NFA
○ ε-NFA
● Aceitam as mesmas linguagens (regulares)
ε-NFA
NFA
DFA
Resumo
“fácil”
Construção de subconjuntos
Construção de 
subconjuntos + 
ECLOSE
É possível simular
Mas cada um tem um 
custo (tamanho da 
engrenagem)
Resumo
● Simular direto vs converter para DFA
○ Depende da aplicação
○ Padrões de busca voláteis (ex: grep)
■ Melhor simular NFA
○ Padrões fixos (ex: análise léxica)
■ Melhor converter para DFA
Fim
Aula 06 - NFA com transições vazias
Slides/LFA.2015.2.Aula07.Implementa��o de Aut�matos Finitos.pdf
Linguagens Formais e 
Autômatos
Aula 07 - Implementação de Autômatos 
Finitos
Prof. Dr. Daniel Lucrédio
Departamento de Computação / UFSCar
Última revisão: ago/2015
Implementando DFAs
● Implementação é simples
● Teste que implementa a função de transição e testa 
o estado final
○ Ou uma implementação com uma tabela genérica
● Demonstração
Implementando DFAs
● www.simuladordeautomatos.com
● IC e TCC
○ UNIUBE – Universidade de Uberaba
Implementando NFAs
● A implementação é mais complexa do que o DFA
○ Mas em essência é o mesmo mecanismo
● Envolve duas estratégias
○ Processamento paralelo
○ “Backtracking”
● Demonstração
Implementando ε-NFAs
● Envolve a implementação do épsilon-fechamento
○ E também precisa de uma coluna para transições 
vazias
● Demonstração
Fim
Aula 07 - Implementação de Autômatos 
Finitos
Slides/LFA.2015.2.Aula08.Express�es Regulares.pdf
Aula 08 - Expressões regulares
Linguagens Formais e 
Autômatos
Prof. Dr. Daniel Lucrédio
Departamento de Computação / UFSCar
Última revisão: ago/2015
Referências bibliográficas
● Introdução à teoria dos autômatos, linguagens e computação / John 
E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman ; tradução da 2.ed. 
original de Vandenberg D. de Souza. - Rio de Janeiro : Elsevier, 2002 
(Tradução de: Introduction to automata theory, languages, and 
computation - ISBN 85-352-1072-5)
○ Capítulo 3 - Seções 3.1 e 3.4
● Introdução à teoria da computação / Michael Sipser ; tradução técnica 
Ruy José Guerra Barretto de Queiroz ; revisão técnica Newton José Vieira. 
-- São Paulo : Thomson Learning, 2007 (Título original : Introduction to the 
theory of computation. "Tradução da segunda edição norte-americana" - 
ISBN 978-85-221-0499-4)
○ Capítulo 1 - Seção 1.3
Expressões regulares
● Autômatos denotam linguagens
● Autômatos possuem duas notações
○ Diagrama de estados
○ Tabela de transições
● Vimos apenas uma notação para linguagens
○ Notações de conjuntos / formadores de conjuntos
○ Ex: {w | regra sobre w}
● Existe outra notação
○ Expressões regulares
Expressões regulares
● Notação algébrica
● Definição de álgebra (by wikipedia)
○ Um conjunto A e uma coleção de operações sobre A
○ Operações k-árias
■ 0-árias: ex: constantes, 2, x, y
■ 1-árias: ex: -10
■ 2-árias: ex: 2+2, 3*y
Expressões regulares
● Na teoria da computação
● Álgebra envolve
○ Conjunto A = alfabeto
○ Operações = operações regulares
● Operações regulares
○ Operações sobre membros de um alfabeto
○ Linguagens regulares são fechadas sob as 
operações regulares
Conjuntos fechados sob uma 
operação
● Exemplo:
○ N = {1,2,3,...} (conjunto de números naturais)
○ N é fechado sob multiplicação
○ Ou seja: para quaisquer x e y em N
■ x * y também está em N
○ N não é fechado sob divisão
■ Contra-exemplo: 1 e 2 estão em N, mas ½ não está!
● Definição:
○ Uma coleção de objetos é fechada sob alguma 
operação se, aplicando-se essa operação a 
membros da coleção, recebe-se um objeto ainda na 
coleção
Operações regulares
● Operações que:
○ Aplicadas sobre elementos de linguagens regulares
○ Resultam em linguagens regulares
● Em outras palavras:
○ Sejam L1 e L2 duas linguagens regulares
○ L1 opreg L2 é regular
Operações regulares
● São 3 as operações regulares:
○ União: A ∪ B = {x | x ∈ A ou x ∈ B}
○ Concatenação: A.B = {xy | x ∈ A e y ∈ B}
○ Estrela (ou fechamento, ou fechamento de Kleene): 
A* = {x1x2...xk | k ≥ 0 e cada xi ∈ A}
● União e concatenação são operações binárias
● Estrela é uma operação unária
Operações regulares
● União
○ L = {001, 10, 111} e M = {ε, 001}
○ L ∪ M = {ε, 10, 001, 111}
● Concatenação
○ L = {001, 10, 111} e M = {ε, 001}
○ L.M (ou LM) = {001,10,111,001001,10001,111001}
● Estrela
○ L = {0, 11}
○ L* = {ε, 0, 00, 000, 000, 11, 011, 1111, 00011011, ... 
(não há uma ordem lógica aqui)}
Operações regulares
● Teorema: A classe de linguagens regulares é 
fechada sob a operação de união
○ Em outras palavras: se A1 e A2 são linguagens 
regulares, A1 ∪ A2 é regular
● Prova:
○ Construção
○ A1 é regular, existe um autômato M1
○ A2 é regular, existe um autômato M2
○ Construímos um autômato M que simula M1 e M2, 
aceitando se uma das simulações aceita
Operações regulares
M1
M2
ε
ε
ε
ε
L(M) = L(M1) ∪ L(M2)
M
Operações regulares
● Teorema: A classe de linguagens regulares é 
fechada sob a operação de concatenação
○ Em outras palavras, se A1 e A2 são linguagens 
regulares, A1.A2 é regular
● Prova:
○ Construção
○ A1 é regular, existe um autômato M1
○ A2 é regular, existe um autômato M2
○ Construímos um autômato M que simula M1 e em 
seguida M2, passando de M1 para M2 quando M1 
aceita, e aceitando quando M2 aceita
Operações regulares
M1
M2
ε
L(M) = L(M1) . L(M2)
M
Operações regulares
● Teorema: A classe de linguagens regulares é 
fechada sob a operação de estrela
○ Em outras palavras, se A é uma linguagem regular, 
A* é regular
● Prova:
○ Construção
○ A é regular, existe um autômato M
○ Construímos um autômato M’ que simula M, com a 
possibilidade de ir direto para o estado de aceitação, 
e a possibilidade de voltar de um estado de 
aceitação para o inicial
Operações regulares
M
ε
L(M’) = L(M)*
M’
ε
ε
ε
Expressões regulares
● Existe ainda uma “quarta operação regular”
○ Constantes (operações 0-árias)
○ A diferença é sutil
● As operações operam sobre conjuntos
○ Mas muitas vezes as usaremos com símbolos
○ Ou seja, em uma concatenação, ao invés de dizer 
{a}.{b}, queremos dizer a.b, ou simplesmente ab
● Por isso, iremos considerar que uma constante é 
uma operação
○ Toma como entrada um símbolo
○ E o resultado é uma linguagem (conjunto), cujo 
único
elemento é aquele símbolo
Expressões regulares
● Conceito de “variáveis”
○ Símbolos que representam linguagens regulares
○ Ex: a.b, onde a = {w | w contém número par de 0s} e 
b = {0,11,101}
Expressões regulares
● Construindo expressões regulares
○ Assim como aritmética
○ Expressões elementares (constantes e/ou variáveis)
○ Operadores que formam expressões mais 
complexas
● Operadores possuem precedência
○ Ex: multiplicação sobre adição, etc
● Métodos para agrupar operadores
○ Ex: parêntesis, colchetes, chaves, etc
Expressões regulares
● Constantes:
○ ε e Ø são expressões regulares
■ L(ε) = {ε}
■ L(Ø) = Ø
○ Se a é um símbolo qualquer, a é uma expressão 
regular
■ L(a) = {a}
● União
○ Se E e F são expressões regulares, E + F é uma 
expressão regular
■ L(E+F) = L(E) ∪ L(F)
Expressões regulares
● Concatenação
○ Se E e F são expressões regulares, EF é uma 
expressão regular
■ L(EF) = L(E).L(F)
● Estrela
○ Se E é uma expressão regular, E* é uma expressão 
regular
■ L(E*) = (L(E))*
● Parêntesis
○ Se E é uma expressão regular, (E) é uma expressão 
regular
■ L((E)) = L(E)
Expressões regulares
● Precedência
○ Estrela → concatenação → união
○ Ex: 01*+1
● Parêntesis
○ Mudam a precedência
○ Ex: (01)*+1 ou 0(1*+1)
Exemplos de expressões regulares
● Alfabeto = {0,1}
○ 0*10* = {w | w contém um único 1}
○ 01 + 10 = {01,10}
○ (ε + 0)1* = {w | w é uma sequência de zero ou mais 
1s, começando opcionalmente com 0}
○ (0+1)* = Conjunto das partes do alfabeto ou 
conjunto de todas as cadeias possíveis sobre o 
alfabeto, incluindo a cadeia vazia (|w| ≥ 0)
○ (0+1)(0+1)* = Idem ao exemplo acima, mas sem a 
cadeia vazia (|w| ≥ 1)
Exercícios
● Escreva expressões regulares correspondentes às 
seguintes linguagens:
○ {w | w começa com um 1 e termina com um 0}
■ Resp: 1(0+1)*0
○ {w | w contém pelo menos três 1s}
■ Resp: 0*10*10*1(0+1)*
○ {w | o comprimento de w é no máximo 5}
■ Resp: (0+1+ε)(0+1+ε)(0+1+ε)(0+1+ε)(0+1+ε)
○ {w | toda posição ímpar de w é um 1}
■ Resp: (1(0+1))* + 1((0+1)1)* ou (1(0+1))*(1+ε)
Leis algébricas para 
expressões regulares
Leis algébricas para expressões 
regulares
● É possível (e muitas vezes necessário) simplificar 
expressões regulares
○ Ex: 1*0 + 1*0(ε+0+1)*(ε+0+1) = 1*0(0+1)*
● Existem algumas leis algébricas que facilitam esse 
processo
Leis algébricas para expressões 
regulares
● Associatividade e comutatividade
○ L+M=M+L
■ Ex: 0+1 = 1+0
○ (L+M)+N=L+(M+N)
■ Ex: (a* + bc) + a = a* + (bc + a)
○ (LM)N=L(MN)
■ Ex: (00(1+0))111=00((1+0)111)
Leis algébricas para expressões 
regulares
● Identidades (elemento neutro) e aniquiladores
● Ø+L=L+Ø=L (Ø é identidade para união)
● εL=Lε=L (ε é identidade para concatenação)
● ØL=LØ=Ø (Ø é aniquilador para concatenação)
● Exs:
● εa(b+c)+aaε = a(b+c)+aa
● Ø(ε+1)*(1+0(01*10(0+1))) + 01 = Ø + 01 = 01
Leis algébricas para expressões 
regulares
● Leis distributivas
○ L(M+N)=LM+LN
○ (M+N)L=ML+NL
■ Exs:
● 0(0+1) = 00 + 01
● (0+1)(0+1) = (0+1)0 + (0+1)1
● (0+1)(0+1) = 0(0+1) + 1(0+1)
Leis algébricas para expressões 
regulares
● Lei da idempotência
○ L+L=L
■ Exs:
● (0+1+ε) + (0+1+ε)=(0+1+ε)
● (0+1+ε)+01*0+(ε+0+1)+(ε+1+0)=(0+1+ε)+01*0
Leis algébricas para expressões 
regulares
● Leis envolvendo fechamentos
○ (L*)*=L*
■ Ex:((01)*)*=(01)*
○ Ø*=ε
○ ε*=ε
● Operadores de fechamento adicionais
○ L+=LL*=L*L
○ L*=L++ε
○ L?=ε+L
Exemplos de simplificação
0+010
0ε+010
0(ε+10)
0(10)?
ab*b(a+ε)
ab*ba?
ab+a?
a+(b+c+ε)a(b+c)+ca+ba
a+(b+c)?a(b+c)+ca+ba
a+(b+c)?a(b+c)+(c+b)a
εa+(b+c)?a(b+c)+(c+b)a
εa+(c+b)a+(b+c)?a(b+c)
(ε+c+b)a+(b+c)?a(b+c)
(b+c)?a+(b+c)?a(b+c)
(b+c)?aε+(b+c)?a(b+c)
(b+c)?a(ε+b+c)
(b+c)?a(b+c)?
Fim
Aula 08 - Expressões regulares
Slides/LFA.2015.2.Aula09.Aut�matos finitos e express�es regulares.pdf
Aula 09 - Autômatos finitos e expressões 
regulares
Linguagens Formais e 
Autômatos
Prof. Dr. Daniel Lucrédio
Departamento de Computação / UFSCar
Última revisão: ago/2015
Referências bibliográficas
● Introdução à teoria dos autômatos, linguagens e computação / John 
E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman ; tradução da 2.ed. 
original de Vandenberg D. de Souza. - Rio de Janeiro : Elsevier, 2002 
(Tradução de: Introduction to automata theory, languages, and 
computation - ISBN 85-352-1072-5)
○ Capítulo 3 - Seção 3.2
● Introdução à teoria da computação / Michael Sipser ; tradução técnica 
Ruy José Guerra Barretto de Queiroz ; revisão técnica Newton José Vieira. 
-- São Paulo : Thomson Learning, 2007 (Título original : Introduction to the 
theory of computation. "Tradução da segunda edição norte-americana" - 
ISBN 978-85-221-0499-4)
○ Capítulo 1 - Seção 1.3
Autômatos finitos e expressões 
regulares
● São diferentes na notação
○ Mas tanto autômatos finitos como expressões 
regulares representam exatamente o mesmo 
conjunto de linguagens
■ Linguagens regulares
● Ou seja:
○ Toda linguagem definida por um autômato finito 
também é definida por uma expressão regular
○ Toda linguagem definida por uma expressão regular 
é definida por um autômato finito
Autômatos finitos e expressões 
regulares
ε-NFA
ER
NFA
DFA
Já demonstrado
A demonstrar
Conversão DFA→ER
● Teorema: Se L = L(A) para algum DFA A, então 
existe uma expressão regular R tal que L = L(R)
● Conversão é surpreendentemente complicada
○ Método 1: n3 expressões, com 4n símbolos (pior 
caso)
○ Método 2: eliminação de estados
■ Mais simples, porém também trabalhosa
■ Envolve uma notação mista: autômatos + ERs
● Autômato finito não-determinístico generalizado
● Transições são expressões regulares
Autômatos + ERs
Conversão DFA→ER
● Método da eliminação de estados
● Eliminamos todos os estados, um por um
○ Ao eliminar um estado s, todos os caminhos que 
passam por s não mais existem no autômato
● Substituiremos símbolos por ER nas transições, 
para representar as transições eliminadas
Conversão DFA→ER
● Para cada estado de aceitação q, elimine todos os 
estados, com exceção de q e q0 (estado inicial)
○ Resultado = um autômato para cada estado de 
aceitação
Conversão DFA→ER
● Cada autômato terá uma ER equivalente
01*(1+0)*110
0+1*
11
1
1(0+ε)10
Conversão DFA→ER
Basta fazer a união de todas as expressões
01*(1+0)*110
0+1*
11
1
1(0+ε)10
01*(1+0)*110 + 0 + 
1* + 111 + 1(0+ε)10
Conversão DFA→ER
Eliminando um estado s (caso não 
haja um determinado arco, 
considerar que existe um arco com 
rótulo Ø)
Conversão DFA→ER
● Repetir esse procedimento para todos os estados
● No final, existem duas possibilidades:
○ q0=q
■ Resta um único estado, com uma transição R
■ R é a expressão regular equivalente
○ q0≠q
■ Restam dois estados, no seguinte formato genérico:
A expressão regular final é (R+SU*T)*SU*
R
R U
S
T
Conversão DFA→ER
● Exemplo: cadeias com símbolo 1 a duas ou três 
posições a partir do final
Conversão DFA→ER
● Primeiro passo, substituir as transições rotuladas 
0,1 por 0 + 1
Conversão DFA→ER
● Eliminando B (assim dá para reaproveitar em 
outras reduções)
○ Q1=1
○ P1=0+1
○ R11=Ø
○ S=Ø
● Arco de A para C = R11+Q1S*P1 = Ø+1Ø*(0+1)
○ Simplificando: 1(0+1)
Conversão DFA→ER
● Eliminando C
○ Q1=1(0+1)
○ P1=0+1
○ R11=Ø
○ S=Ø
● Arco de A para D = R11+Q1S*P1 = Ø+1(0+1)Ø*
(0+1)
○ Simplificando: 1(0+1)(0+1)
Conversão DFA→ER
● Restou um autômato de 2 estados
○ R=0+1
○ S=1(0+1)(0+1)
○ U=Ø
○ T=Ø
● Fórmula: (R+SU*T)*SU*
○ Resultado: (0+1+1(0+1)(0+1)Ø*Ø)*1(0+1)(0+1)Ø*
○ Simplificando: (0+1)*1(0+1)(0+1)
R U
S
T
Conversão DFA→ER
● Eliminando D agora
○ Não há sucessor, portanto não haverá mudanças de 
arcos
○ Da mesma forma, restou um autômato de 2 estados
■ Expressão regular resultante: (0+1)*1(0+1)
Conversão DFA→ER
● Haviam dois estados de aceitação
○ Foram obtidos dois autômatos
■ Duas expressões regulares equivalentes
● A expressão regular final é a união dessas duas:
● (0+1)*1(0+1)+(0+1)*1(0+1)(0+1)
● Simplificando
○ (0+1)*1(0+1)(0+1)?
Conversão ER→ε-NFA
● Teorema: Toda linguagem definida por uma 
expressão regular também é definida por um 
autômato finito
● Prova por construção: ER→ε-NFA
○ Base + indução
● Base: ε, Ø e a (um símbolo qualquer)
ε
a
Conversão ER→ε-NFA
● Indução: Os mesmos autômatos das provas sobre 
o fechamento das operações regulares 
R
S
ε
ε
ε
ε
R
S
ε
Rε
M’
ε
ε
ε
R+S RS
R*
Conversão ER→ε-NFA
● Características do ε-NFA:
○ Possui exatamente um estado de aceitação
○ Nenhum arco chega no estado inicial
○ Nenhum arco sai do estado de aceitação
Conversão ER→ε-NFA
● Ex: (0+1)*1(0+1)
Fim
Aula 09 - Autômatos finitos e expressões 
regulares
Slides/LFA.2015.2.Aula11.Linguagens n�o regulares.pdf
Aula 11 - Linguagens não regulares
Linguagens Formais e 
Autômatos
Prof. Dr. Daniel Lucrédio
Departamento de Computação / UFSCar
Última revisão: ago/2015
Referências bibliográficas
● Introdução à teoria dos autômatos, linguagens e computação / John 
E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman ; tradução da 2.ed. 
original de Vandenberg D. de Souza. - Rio de Janeiro : Elsevier, 2002 
(Tradução de: Introduction to automata theory, languages, and 
computation - ISBN 85-352-1072-5)
○ Capítulo 4 - Seção 4.1
● Introdução à teoria da computação / Michael Sipser ; tradução técnica 
Ruy José Guerra Barretto de Queiroz ; revisão técnica Newton José Vieira. 
-- São Paulo : Thomson Learning, 2007 (Título original : Introduction to the 
theory of computation. "Tradução da segunda edição norte-americana" - 
ISBN 978-85-221-0499-4)
○ Capítulo 1 - Seção 1.4
Linguagens não regulares
● Até agora vimos que: linguagens regulares são 
aquelas reconhecidas por autômatos finitos
○ Não foi feita nenhuma definição do que é uma 
linguagem regular
○ Um ser humano, ao olhar para uma linguagem, 
dificilmente consegue dizer se é ou não regular
○ Na verdade, não existe tal definição
● Mas existe uma distinção
○ Linguagens regulares vs não-regulares
○ A linha divisória é o fato de que
■ Autômatos finitos não conseguem contar
Linguagens não regulares
● Linguagens que exigem um contador
○ Ex: comentários dentro de comentários, escopos 
aninhados em uma linguagem, parêntesis 
aninhados, etc
○ Ex:
■ (1+2*(3-5+(7*7))-6)
■ É preciso contar quantos parêntesis são abertos e quantos 
são fechados
● Tente imaginar um autômato que reconheça tais 
cadeias
○ Estados são a “memória” do autômato
Linguagens não regulares
● Para reconhecer 
infinitos níveis de 
parêntesis aninhados, 
seriam necessários 
infinitos estados
0
1(
)
Σ Σ
2(
)
Σ
∞
...
Linguagens não regulares
● Outros exemplos:
○ {0n1n|n≥0}
○ {w|w tem número igual de 0s e 1s}
○ {ww| w seja uma cadeia sobre qualquer alfabeto}
● Mas veja esse exemplo:
○ {w|w tem um número igual de ocorrências de 01 e 10 
como subcadeias}
○ Aparentemente, precisa contar
■ Mas essa linguagem é regular! (faça depois como exercício a 
prova, se duvidar)
● Formalmente:
○ Lema do bombeamento para linguagens regulares
○ Permite definir exatamente quais linguagens não são 
regulares
Lema do bombeamento para 
linguagens regulares
● Formalmente:
○ Se A é uma linguagem regular, então existe um 
número p (o comprimento de bombeamento) tal que, 
se s é qualquer cadeia de A de comprimento no 
mínimo p, então s pode ser dividida em três partes, 
s=xyz, satisfazendo as seguintes condições:
■ Para cada i ≥ 0, xyiz ∈ A
■ |y| > 0
■ |xy| ≤ p
● Informalmente:
○ Toda cadeia da linguagem contém uma parte que 
pode ser repetida um número qualquer de vezes 
(bombeada), com a cadeia resultante 
permanecendo na linguagem
Lema do bombeamento para 
linguagens regulares
● Essa repetição ou bombeamento é a característica que 
faz com que seja sempre possível definir um número 
finito de estados para um autômato que reconheça a 
linguagem
● Uso do lema do bombeamento:
○ Provar que B não é regular
○ Contradição: suponha que B seja regular
○ 1. Encontre um p de forma que todas as cadeias de 
comprimento p ou maiores possam ser bombeadas
○ 2. Encontre uma cadeia s em B que tenha comprimento p 
ou mais, mas que não possa ser bombeada
○ 3. Demonstre que s não pode ser bombeada 
considerando todas as maneiras de dividir s em x,y e z, 
conforme o lema
Lema do bombeamento para 
linguagens regulares
● Ex: {0n1n|n≥0}
○ 1. Seja p o comprimento de bombeamento
○ 2. Escolha s = 0p1p
■ s é maior que p (conforme o lema)
■ Portanto, o lema diz que s pode ser dividida em 3 partes, 
s=xyz, onde para qualquer i ≥ 0, xyiz está em B
● Ou seja, deve ser possível “bombear” y
○ 3. Mas é impossível!!
■ Primeira possibilidade: Suponha que y contém apenas 0s
● Ex: s = 000111, x=0, y=00, z=111
● Sempre que bombearmos y, teremos como resposta 
uma cadeia que não pertence à linguagem
● Pois teremos como resultado mais 0s do que 1s
Lema do bombeamento para 
linguagens regulares
● Ex: {0n1n|n≥0}
○ 3. Mas é impossível!! (continuação)
■ Segunda possibilidade: Suponha que y contém apenas 1s
● Ex: s = 000111, x=000, y=11, z=1
● Sempre que bombearmos y, teremos como resposta 
uma cadeia que não pertence à linguagem
● Pois teremos como resultado mais 1s do que 0s
■ Terceira possibilidade: y contém 0s e 1s
● Ex: s = 000111, x=00, y=01, z=11
● Sempre que bombearmos y, teremos como resposta 
uma cadeia que não pertence à linguagem
● Pois teremos como resultado a presença de 0s e 1s 
alternados
Lema do bombeamento para 
linguagens regulares
● Ex: {0n1n|n≥0}
○ Ou seja, é impossível existir uma divisão de s de 
acordo com o lema do bombeamento
○ Isso é uma contradição!
● Ou seja, se não fizemos nada de errado, a 
suposição de que B é regular é falsa
○ Portanto, B não é regular
Lema do bombeamento para 
linguagens regulares
● O “truque” é encontrar o s
● Requer um pouco de pensamento criativo
● Tentativa e erro
● Busca pela “essência” da não-regularidade de B
● Conhecimento das restrições do lema
○ (|y| > 0, |xy| ≤ p, etc)
Linguagens não regulares
● Ok, descobri que uma linguagem não é regular
○ Como resolver o problema?
○ Como obter uma implementação?
● Bom, se o problema é que um autômato finito não 
consegue contar...
○ ... basta adicionar um contador!
● Essa é exatamente a solução
○ Mais poder aos autômatos
○ Classe maior de linguagens
○ Mais detalhes nas próximas aulas!
Fim
Aula 11 - Linguagens não regulares
Slides/LFA.2015.2.Aula12.Linguagens.Livres.De.Contexto.pdf
Linguagens Formais e 
Autômatos
Aula 12 - Linguagens Livres de Contexto
Prof. Dr. Daniel Lucrédio
Departamento
de Computação / UFSCar
Última revisão: ago/2015
Referências bibliográficas
● Introdução à teoria dos autômatos, linguagens e computação / John E. 
Hopcroft, Rajeev Motwani, Jeffrey D. Ullman ; tradução da 2.ed. original de 
Vandenberg D. de Souza. - Rio de Janeiro : Elsevier, 2002 (Tradução de: 
Introduction to automata theory, languages, and computation - ISBN 85-352-
1072-5)
○ Capítulo 5 - Seções 5.1, 5.2 e 5.3
● Introdução à teoria da computação / Michael Sipser ; tradução técnica 
Ruy José Guerra Barretto de Queiroz ; revisão técnica Newton José Vieira. -- 
São Paulo : Thomson Learning, 2007 (Título original : Introduction to the 
theory of computation. "Tradução da segunda edição norte-americana" - 
ISBN 978-85-221-0499-4)
○ Capítulo 2 - Seção 2.1
Linguagens livres de contexto
● Linguagens regulares permitem descrever muitas 
coisas práticas
○ Ex: busca textual, mecanismos simples de 
comunicação, máquinas e protocolos simples
● Mas são limitadas
○ “Não conseguem contar” → autômatos finitos
● Mas e se adicionarmos um contador aos autômatos 
finitos?
Linguagens livres de contexto
Entrada
q6
13
+ -
Linguagens livres de contexto
● Ex: anbn
q0 q2q1
q3
a, ++
b, --
a
C=0?
b, --
Linguagens livres de contexto
● Uma classe maior de linguagens
○ Linguagens livres de contexto
● Inicialmente, foram uma maneira de entender a 
linguagem humana
○ Gramáticas livres de contexto
■ Formalização das regras gramaticais da linguagem humana
● Característica principal: recursão
○ Ex: linguagens naturais: frases nominais dentro de 
frases verbais, e vice-versa
● O Brasil foi campeão da copa do mundo de futebol
○ Sujeito, predicado, verbo, objeto direto, etc...
Linguagens livres de contexto
● Entendendo um pouco mais:
○ As linguagens humanas possuem símbolos
■ Palavras
○ Possuem também regras
■ Gramática (português, inglês, etc)
○ Existem frases válidas e inválidas
● Ex:
○ O Brasil foi campeão da copa do mundo de futebol
○ Campeão da mundo do foi futebol o de copa Brasil
Linguagens livres de contexto
● A partir do estudo da linguagem humana, chegou-se 
a um modelo matemático formal sobre uma classe de 
linguagens
● O conceito é o mesmo das linguagens regulares
● Linguagens = problemas
● Um problema é:
○ Dada uma cadeia, determinar se pertence ou não à linguagem
○ A diferença é que aqui, o conceito cadeia é diferente ...
○ ... e as regras de definição da linguagem são mais poderosas do 
que simples transições em um autômato finito
Linguagens livres de contexto
● Linguagens regulares:
○ Base: símbolos de um alfabeto
○ Regras (“gramática”): expressões 
regulares
○ Característica: 
■ estados finitos / não conseguem 
contar / lema do bombeamento para 
linguagens regulares
● Linguagens livres de contexto:
○ Base: símbolos terminais
■ Pode-se pensar que um símbolo 
terminal é um símbolo de um 
alfabeto
■ Mas cada símbolo terminal pode ser 
uma cadeia sobre uma linguagem 
regular (uma palavra)
○ Regras (“gramática”): gramáticas livres de 
contexto
○ Característica:
■ recursão simples / consegue contar 
(de forma limitada) / lema do 
bombeamento para linguagens 
livres de contexto
Gramáticas livres de contexto
Gramáticas livres de contexto
● Gramática: a melhor forma de “ver” uma linguagem 
(ex: ER melhor do que autômatos finitos)
○ No caso das linguagens livres de contexto, temos as 
gramáticas livres de contexto
A → 0A1
A → B
B → #
Regras de substituição ou
produções
Gramáticas livres de contexto
A → 0A1
A → B
B → #
Lado esquerdo ou cabeça: 
sempre um único símbolo. Esses 
símbolos são chamados de 
variáveis ou não-terminais
Lado direito ou corpo: uma 
cadeia de símbolos. Podem ter 
variáveis e outros símbolos, 
chamados de terminais
Uma das variáveis é designada como a variável ou símbolo inicial. 
É a variável que aparece do lado esquerdo da primeira regra. 
(Neste exemplo, A é o símbolo inicial)
Gramáticas livres de contexto
A → 0A1
A → B
B → #
Sempre que houver mais de uma produção para uma mesma 
variável, podemos agrupá-las com o símbolo “|”. 
A → 0A1 | B
B → #
Gramáticas livres de contexto
● Variáveis normalmente são representadas por letras maiúsculas (A,B,
C, ....)
● Terminais normalmente são representados por letras minúsculas, 
números, símbolos, etc... (a,b,c,0,1,2,#,...)
○ Assim como nos alfabetos que estudamos até então
● Mas na prática usamos nomes mais significativos
Exemplo
OraçãoSubstantiva → SubstantivoComplexo
 | SubstantivoComplexo FrasePreposicional ;
FraseVerbal → VerboComplexo
 | VerboComplexo FrasePreposicional ;
FrasePreposicional → Preposição SubstantivoComplexo ;
SubstantivoComplexo → Artigo Substantivo | OraçãoSubstantiva ;
VerboComplexo → Verbo | Verbo OraçãoSubstantiva ;
Artigo → o | a | um | uma | ε ;
Substantivo → armário | funcionário | gerente | cadeira | braços | aço ;
Verbo → gosta | brinca | olha ;
Preposição → para | com | de | sem ;
Gramáticas livres de contexto
● Terminais podem ser cadeias (sequências) simples:
○ Ex: “menino”, “if”, “while”, “int”, “char”, etc...
● Podem também ser cadeias descritas com linguagens 
regulares (ex: compiladores)
○ Ex: 
■ [a-zA-Z][a-zA-Z0-9]* : identificadores válidos de uma 
linguagem de programação
● Ex: posX1, valorAluguel, rgCliente
■ “[^”]*” : literais do tipo string
● Ex: “Telefone:”, “Digite o texto abaixo”, 
“Ocorreu um erro”
■ [0-9]+ : números inteiros
Gramáticas livres de contexto
● Definição formal
G = (V,T,P,S)
V = conjunto de variáveis
T = conjunto de terminais
P = conjunto de produções
S = símbolo inicial
● Ex:
Gpalíndromos = ({P},{0,1},A,P)
A = {
P → ε
P → 0
P → 1
P → 0P0
P → 1P1
}
Gramáticas livres de contexto
● Como uma gramática descreve uma 
linguagem?
● Duas formas:
○ Inferência recursiva
○ Derivação
● Ex: Gramática para expressões 
aritméticas
○ V = {E,I}
○ T = {+,*,(,),a,b,0,1}
○ P = conjunto de regras ao lado
○ S = E
E → I
E → E + E
E → E * E
E → (E)
I → a
I → b
I → Ia
I → Ib
I → I0
I → I1
Gramáticas livres de contexto
● Inferência recursiva
○ Dada uma cadeia (conjunto de símbolos terminais)
○ Do corpo para a cabeça
● Ex: a*(a+b00)
○ a*(a+b00) ⇐ a*(a+I00) ⇐ a*(a+I0) ⇐ a*(a+I) ⇐ a*(a+E) 
⇐ a*(I+E) ⇐ a*(E+E) ⇐ a*(E) ⇐ a*E ⇐ I*E ⇐ E*E ⇐ E
Gramáticas livres de contexto
● Derivação
○ Dada uma cadeia (conjunto de símbolos terminais)
○ Da cabeça para o corpo
● Ex: a*(a+b00)
○ E ⇒ E*E ⇒ I*E ⇒ a*E ⇒ a*(E) ⇒ a*(E+E) ⇒ a*(I+E) ⇒ a*(a+E) ⇒ a*
(a+I) ⇒ a*(a+I0) ⇒ a*(a+I00) ⇒ a*(a+b00)
● Símbolo de derivação: ⇒
● Derivação em múltiplas etapas: ⇒* (obs: asterisco acima da seta)
○ E ⇒* a*(E)
○ a*(E+E) ⇒* a*(a+I00)
○ E ⇒* a*(a+b00)
Gramáticas livres de contexto
● Derivações mais à esquerda
○ Sempre substituir a variável mais à esquerda
○ Notação: ⇒lm, ⇒
*
lm
● Derivações mais à direita
○ Sempre substituir a variável mais à direita
○ Notação: ⇒rm, ⇒
*
rm
Formas sentenciais
● Derivações a partir do símbolo inicial
● Formas sentenciais à esquerda
○ Obtidas somente com derivações mais à esquerda
● Formas sentenciais à direita
○ Obtidas somente com derivações mais à direita
Ex: E ⇒lm E*E ⇒lm I*E ⇒lm a*E ⇒lm a*(E)
Ex: E ⇒rm E*E ⇒rm E*(E) ⇒rm a*(E+E) ⇒rm a*
(E+I)
Exercícios
● Dada a gramática descrita pelas produções

Teste o Premium para desbloquear

Aproveite todos os benefícios por 3 dias sem pagar! 😉
Já tem cadastro?

Outros materiais