LFA I - Manual

Prévia do material em texto

INSTITUTO SUPERIOR DE CIÊNCIAS E TECNOLOGIA 
DE MOÇAMBIQUE 
 
 
 
 
Linguagens Formais e Autómatos I 
(Parte Teórica, 93 Exemplos e Problemas resolvidos. 56 Problemas propostos com 
respostas) 
 
 
 
 
Boris Tanana 
 
 
 
 
 
 
 
Maputo, 2019 
ii 
Índice 
 
INTRODUÇÃO .............................................................................................................................. 5 
Capítulo 1 ........................................................................................................................................ 6 
Preliminares Relações binárias. Funções .................................................................................... 6 
Conjuntos finitos e infinitos. Cardinalidades .............................................................................. 8 
Capítulo 2 ........................................................................................................................................ 9 
Linguagens Formais. Conceitos básicos ..................................................................................... 9 
Operações sobre as palavras ..................................................................................................... 10 
Ordenação das palavras............................................................................................................. 12 
Ordem lexicográfica.................................................................................................................. 12 
Ordem canónica ........................................................................................................................ 12 
Operações sobre linguagens ...................................................................................................... 14 
Problemas resolvidos ................................................................................................................ 16 
Problemas propostos ................................................................................................................. 17 
Respostas................................................................................................................................... 18 
Capítulo 3 ...................................................................................................................................... 19 
Linguagens Regulares. Expressões Regulares .......................................................................... 19 
Problema de representação finita de linguagens ....................................................................... 19 
Linguagens Regulares (LR) ...................................................................................................... 19 
Expressões Regulares (ER) ....................................................................................................... 20 
Propriedades das ER’s .............................................................................................................. 22 
Problemas propostos ................................................................................................................. 23 
Respostas................................................................................................................................... 24 
Capítulo 4 ...................................................................................................................................... 26 
Autómatos Finitos Determinísticos........................................................................................... 26 
Diagrama de transição de um AFD ........................................................................................... 27 
Caminho de computação ........................................................................................................... 28 
Extensão da função de transição ............................................................................................... 29 
Linguagem reconhecida (aceite) por um AFD.......................................................................... 30 
Problemas resolvidos ................................................................................................................ 36 
Problemas propostos ................................................................................................................. 39 
iii 
Respostas................................................................................................................................... 40 
Capítulo 5 ...................................................................................................................................... 45 
Autómatos Finitos Não Determinísticos com 𝝀 – arcos ........................................................... 45 
𝝀 – Fecho................................................................................................................................... 53 
Simulação de um AFND – 𝝀 por um AFD ............................................................................... 54 
Problemas resolvidos ................................................................................................................ 57 
Problemas propostos ................................................................................................................. 60 
Respostas................................................................................................................................... 62 
Capítulo 6 ...................................................................................................................................... 64 
Autómatos Finitos e Expressões Regulares .............................................................................. 64 
Algoritmo de eliminação de estados ......................................................................................... 66 
Problemas resolvidos ................................................................................................................ 67 
Problemas propostos ................................................................................................................. 75 
Respostas................................................................................................................................... 76 
Capítulo 7 ...................................................................................................................................... 78 
Minimização de Autómatos Finitos Determinísticos. Lema de Repetição para LR’s .............. 78 
Construção de AFD mínimo ..................................................................................................... 79 
Lema de Repetição para LR’s ................................................................................................... 80 
Problemas resolvidos ................................................................................................................ 81 
Problemas propostos ................................................................................................................. 86 
Respostas................................................................................................................................... 88 
Capítulo 8 ...................................................................................................................................... 89 
Gramáticas e Linguagens Formais. A hierarquia de Chomsky. Autómatos e Gramáticas 
Regulares................................................................................................................................... 89 
Hierarquia de Chomsky ............................................................................................................ 92 
Autómatos e Gramáticas Regulares ..........................................................................................93 
Problemas resolvidos ................................................................................................................ 96 
Problemas propostos ................................................................................................................. 98 
Respostas................................................................................................................................... 99 
Capítulo 9 .................................................................................................................................... 101 
Gramáticas Independentes de Contexto. Árvores de Derivação. Ambiguidade ..................... 101 
Árvores de derivação. Derivações esquerda e direita. Ambiguidade .................................... 103 
Representação de produções por árvores ................................................................................ 103 
iv 
Derivações esquerdas e direitas .............................................................................................. 107 
Eliminação de ambiguidade .................................................................................................... 109 
Linguagens inerentemente ambíguas ...................................................................................... 111 
Lema de Repetição para linguagens independentes de contexto ............................................ 112 
Problemas resolvidos .............................................................................................................. 113 
Problemas propostos ............................................................................................................... 117 
Respostas................................................................................................................................. 118 
Capítulo 10 .................................................................................................................................. 120 
Autómatos de Pilha ................................................................................................................. 120 
Problemas resolvidos .............................................................................................................. 124 
Problemas propostos ............................................................................................................... 126 
Respostas................................................................................................................................. 127 
Bibliografia ................................................................................................................................. 129 
 
 
 
 
 
 
 
 
 
 Linguagens Formais e Autómatos 
5 
INTRODUÇÃO 
 
 O conceito de linguagem formal começou por ser introduzido pelos linguistas, nos anos 50 
do século XX, com o objectivo de criarem um modelo matemático das linguagens naturais. A 
teoria das linguagens formais tornou-se muito importante quando surgiram as linguagens artificiais 
na ciência da computação. 
 As linguagens de programação permitem abreviar toda a “maquinaria” necessária em 
linguagem-computador para efectuar uma operação. Levantam-se no entanto, vários problemas, 
por exemplo, tradução de linguagens de programação para linguagem máquina ou especificação 
de linguagem de programação. 
 A primeira situação ocorre, por exemplo, na compilação dum programa fonte: define-se 
formalmente o compilador e estudam-se as diversas fases de compilação. Nesta cadeira damos 
alguns tópicos que nos permitirão mais tarde fazer isso. 
 Ao longo dos anos 50 do século XX, os compiladores foram considerados programas 
notoriamente difíceis de se escrever. O primeiro compilador Fortran, por exemplo, consumiu 18 
homens-ano para implementar. Descobrimos desde então, técnicas sistemáticas para o tratamento 
de muitas das importantes tarefas que ocorrem durante a compilação. Igualmente, foram 
desenvolvidas boas linguagens de implementação, ambientes de programação e ferramentas de 
software. 
 Com esses avanços, até mesmo um compilador substancial pode ser escrito num projecto 
de estudantes com duração de um semestre. 
 
 
 
 Linguagens Formais e Autómatos 
6 
Capítulo 1 
 
Preliminares 
Relações binárias. Funções 
 
Sejam 𝐴 e 𝐵 conjuntos, 𝑎 ∈ 𝐴, 𝑏 ∈ 𝐵. Chama-se par ordenado ao objecto (𝑎, 𝑏). 
Dizemos que 𝒂 é a primeira componente de (𝑎, 𝑏) e 𝒃 é a segunda componente de (𝑎, 𝑏). Dois 
pares ordenados (𝑎, 𝑏) e (𝑐, 𝑑) são iguais (𝑎, 𝑏) = (𝑐, 𝑑) se e só se 𝑎 = 𝑐 e 𝑏 = 𝑑. 
 O produto cartesiano de dois conjuntos 𝐴 e 𝐵, denota-se por 𝐴 × 𝐵, é o conjunto de 
todos os pares ordenados (𝑎, 𝑏) com 𝑎 ∈ 𝐴, 𝑏 ∈ 𝐵 
𝐴 × 𝐵 = {(𝑎, 𝑏) | 𝑎 ∈ 𝐴, 𝑏 ∈ 𝐵}. 
Uma relação binária 𝑅 de um conjunto 𝐴 em um conjunto 𝐵 é um subconjunto de 𝐴 × 𝐵 
𝑅 ⊆ 𝐴 × 𝐵. 
Uma relação binária 𝑅 num conjunto 𝐴 é um subconjunto de 𝐴 × 𝐴 = 𝐴2 
𝑅 ⊆ 𝐴2. 
Seja 𝑅 ⊆ 𝐴2. 
𝑅 diz-se reflexiva se (𝑎, 𝑎) ∈ 𝑅, para todo o 𝑎 ∈ 𝐴. 
∀𝑎 ∈ 𝐴, (𝑎, 𝑎) ∈ 𝑅. 
𝑅 diz-se simétrica se para quaisquer 𝑎, 𝑏 ∈ 𝐴 tais que (𝑎, 𝑏) ∈ 𝑅, se tem (𝑏, 𝑎) ∈ 𝑅. 
∀𝑎, 𝑏 ∈ 𝐴 (𝑎, 𝑏) ∈ 𝑅 ⇒ (𝑏, 𝑎) ∈ 𝑅. 
𝑅 diz-se transitiva se para quaisquer 𝑎, 𝑏, 𝑐 ∈ 𝐴 tais que (𝑎, 𝑏) 𝑒 (𝑏, 𝑐) ∈ 𝑅, se tem 
(𝑎, 𝑐) ∈ 𝑅. 
∀𝑎, 𝑏, 𝑐 ∈ 𝐴 (𝑎, 𝑏) ∈ 𝑅 ∧ (𝑏, 𝑐) ∈ 𝑅 ⇒ (𝑎, 𝑐) ∈ 𝑅. 
 Linguagens Formais e Autómatos 
7 
𝑅 diz-se relação de equivalência se 𝑅 for simultaneamente reflexiva, simétrica e 
transitiva. 
Dada uma relação de equivalência 𝑅 num conjunto 𝐴, designemos por [𝑎]𝑅 a classe de 
equivalência de 𝑎 ∈ 𝐴, isto é, o conjunto de todos elementos 𝑥 ∈ 𝐴 tais que (𝑎, 𝑥) ∈ 𝑅 
[𝑎]𝑅 = {𝑥 | (𝑎, 𝑥) ∈ 𝑅}. 
Por 𝐴 𝑅⁄ designa-se o conjunto de todas as classes de equivalência 𝑅 em 𝐴 e chama-se conjunto 
quociente 
𝐴 𝑅⁄ = {[𝑎]𝑅|𝑎 ∈ 𝐴}. 
Note-se que cada classe de equivalência é não vazia; classes de equivalência são disjuntas; 𝐴 é 
uma união das classes de equivalência determinadas por 𝑅. 
Uma função dum conjunto 𝐴 num conjunto 𝐵 é uma relação binária 𝑅 ⊆ 𝐴 × 𝐵 tal que 
para cada 𝑎 ∈ 𝐴 existe exactamente um par ordenado em 𝑅 com primeira componente 𝑎. 
Tal como é hábito escrevermos 𝑓: 𝐴 → 𝐵 para indicar que 𝑓 é uma função de 𝐴 em 𝐵 e 
escrevemos 𝑓(𝑎) = 𝑏 para indicar que (𝑎, 𝑏) ∈ 𝑓. 
Uma função 𝑓: 𝐴 → 𝐵 diz-se: 
• Injectiva – se dados dois elementos distintos 𝑎1, 𝑎2 ∈ 𝐴, se tem 𝑓(𝑎1) ≠ 𝑓(𝑎2); 
• Sobrejectiva – se para cada 𝑏 ∈ 𝐵, existe 𝑎 ∈ 𝐴 tal que 𝑓(𝑎) = 𝑏; 
• Bijectiva – se é simultaneamente injectiva e sobrejectiva. 
Toda a relação binária 𝑅 ⊆ 𝐴 × 𝐵 tem uma inversa 𝑅−1 ⊆ 𝐵 × 𝐴 definida por 
𝑅−1 = {(𝑏, 𝑎) | (𝑎, 𝑏) ∈ 𝑅}. 
Recordemos que no entanto, nem sempre a relação inversa de uma função é uma função. 
Mas se 𝑓: 𝐴 → 𝐵 é uma bijecção então a inversa, 𝑓−1: 𝐵 → 𝐴 é uma função. De facto, 𝑓−1 é uma 
bijecção de 𝐵 em 𝐴. 
 
 Linguagens Formais e Autómatos 
8 
Conjuntos finitos e infinitos. Cardinalidades 
 
 Dois conjuntos 𝐴 e 𝐵 se dizem equipotentes se existe uma bijecção 𝑓: 𝐴 → 𝐵. A relação 
de equipotência é uma relação de equivalência. As classes desta equivalência são cardinalidades 
de conjuntos que pertencem a essa classe. 
Cardinalidade de um conjunto 𝐴 designa-se por |𝐴|. Assim, |𝐴| = |𝐵| ⇔ ∃ 𝑓: 𝐴 → 𝐵, 𝑓 é uma 
bijecção. 
 Um conjunto 𝐴 diz-se finito se é equipotente a {1, 2, … , 𝑛}, para algum 𝑛 ∈ ℕ. 
 Se 𝐴 é equipotente a {1, 2, … , 𝑛} então |𝐴| = 𝑛. Portanto a cardinalidade dum conjunto 
finito é o seu número de elementos. 
 Um conjunto diz-se infinito se não é finito. Como sabemos, os conjuntos ℕ, ℤ, ℚ e ℝ são 
infinitos.No entanto, nem todos os conjuntos infinitos são equipotentes. 
 Um conjunto 𝐴 diz-se enumerável (ou numerável ou contável) se 𝐴 é finito ou 
equipotente ao conjunto ℕ. 
 Um conjunto 𝐴 diz-se infinito enumerável se 𝐴 é equipotente a ℕ, i.é |𝐴| = |ℕ|. 
A cardinalidade de ℕ designa-se por ℵ0 (alefe-zero). 
Prova-se que |ℕ| = |ℤ| = |ℚ| = ℵ0 e que ℝ não é enumerável |ℝ| = ℂ (contínuo). 
Prova-se ainda que: 
• A união de um número finito de conjuntos enumeráveis é um conjunto enumerável; 
• A união duma colecção infinita enumerável de conjuntos enumeráveis é um conjunto 
infinito enumerável. 
Finalmente, formulamos o famoso 
Teorema (de Cantor) 
Seja 𝐴 conjunto qualquer. Então |𝐴| < |𝑃(𝐴)|. 
Também prova-se que |𝑃(ℕ)| = ℂ. 
 Linguagens Formais e Autómatos 
9 
Capítulo 2 
 
Linguagens Formais. Conceitos básicos 
 
Definição 2.1. Um alfabeto é qualquer conjunto finito não vazio. De costume designa-se por Σ. 
Os elementos de Σ chamam-se letras (ou símbolos). 
Uma palavra sobre um alfabeto Σ é uma sequência finita de letras do alfabeto Σ. 
 Vamos usar uma notação simplificada para palavra, omitindo parêntesis e vírgulas. 
Escrevemos 𝑎1𝑎2 … 𝑎𝑛 em vez de (𝑎1, 𝑎2, … , 𝑎𝑛). Identificamos uma palavra que contenha só 
uma letra com a própria letra. 
 A sequência vazia chamamos palavra vazia. Denotamos geralmente essa palavra por 
𝜆 (𝜆 ∉ Σ). 
Exemplo 2.1. 
Σ1 = {𝑎, 𝑏, 𝑐, … , 𝑧} − alfabeto romano; 
Σ2 = {0, 1, … ,9, +, −,÷,×, (, )} − alfabeto de aritmética; 
Σ3 = {0, 1} − alfabeto binário; 
Σ4 = {𝑎, 𝑏, 𝑐, … , 𝑧, 0,1, … , 9, 𝑏𝑒𝑔𝑖𝑛, 𝑒𝑛𝑑, 𝑖𝑓, 𝑜𝑟, … } − alfabeto de Pascal. 
𝑎, 𝑎𝑎, 𝑎𝑏𝑐, 𝑐𝑎𝑏𝑜, 𝜆 − palavras sobre Σ1; 
(2 + 3) × 5, +)(3, 𝜆 − palavras sobre Σ2; 
0, 10, 111, 𝜆 − palavras sobre Σ3; 
𝑏𝑒𝑔𝑖𝑛 
 𝑓𝑜𝑟 𝑖 ≔ 1 𝑡𝑜 3 𝑑𝑜 
 𝑥 ≔ 𝑥 + 1 
𝑒𝑛𝑑 
 
− palavra sobre Σ4 
 Linguagens Formais e Autómatos 
10 
Definição 2.2. O comprimento duma palavra 𝑤 é o seu comprimento como sequência (ou número 
das letras com repetições que representam 𝑤). Designemos por |𝑤| o comprimento da palavra 𝑤. 
Exemplo 2.2. 
|𝑎𝑏𝑐| = 3, |𝑎𝑏| = 2, |𝜆| = 0 (alfabeto Σ1, Exemplo 2.1); 
|𝑏𝑒𝑔𝑖𝑛| = 1 (alfabeto Σ4, Exemplo 2.1). 
 
Definição 2.3. Duas palavras 𝑢 = 𝑎1𝑎2 … 𝑎𝑛 e 𝑣 = 𝑏1𝑏2 … 𝑏𝑘 são iguais se |𝑢| = |𝑣| (𝑛 = 𝑘) 
e 𝑎1 = 𝑏1, 𝑎2 = 𝑏2, … , 𝑎𝑛 = 𝑏𝑛 
𝑢 = 𝑣 ⇔ |𝑢| = |𝑣| ∧ 𝑎1 = 𝑏1, 𝑎2 = 𝑏2, … , 𝑎𝑛 = 𝑏𝑛. 
Por exemplo, 𝑎𝑏 ≠ 𝑏𝑎. 
 
Operações sobre as palavras 
 
 Definição 2.4. A concatenação (ou produto) das palavras 𝑢 = 𝑎1𝑎2 … 𝑎𝑛 e 𝑣 = 𝑏1𝑏2 … 𝑏𝑘 é a 
palavra 𝑢𝑣 = 𝑎1𝑎2 … 𝑎𝑛 𝑏1𝑏2 … 𝑏𝑘. 
 
 
Por exemplo, 𝑢 = 𝑎𝑏, 𝑣 = 𝑏𝑎. 
𝑢𝑣 = 𝑎𝑏𝑏𝑎 
𝑣𝑢 = 𝑏𝑎𝑎𝑏 
Podemos ver que em geral 𝑢𝑣 ≠ 𝑣𝑢. 
 
Definição 2.5. Seja 𝑢 uma palavra. Utilizando a concatenação podemos definir potências de 𝑢 
𝑢0 = 𝜆, 𝑢𝑛+1 = 𝑢𝑛 𝑢, 𝑛 ≥ 0 
u v 𝑢𝑣 = 
 
 Linguagens Formais e Autómatos 
11 
Definição 2.6. Seja 𝑢 = 𝑎1𝑎2 … 𝑎𝑛−1𝑎𝑛. A palavra inversa de 𝑢 é 𝑢
𝑅 = 𝑎𝑛𝑎𝑛−1 … 𝑎2𝑎1. 
Definição 2.7. Uma palavra tal que 𝑢 = 𝑢𝑅 chama-se palíndromo. 
Exemplo 2.3. 
𝜆, 𝑎, 𝑎𝑏𝑎 − são palíndromos; 
𝑎𝑏, 𝑎𝑎𝑏 − não são palíndromos. 
Exemplo 2.4. (Uma piada) 
Primeira frase do mundo é um palindromo. 
Esta frase é: “Madam I’m Adam”. 
 
Teorema 2.1. Sejam 𝑢, 𝑣, 𝑤 palavras quaisquer. 
1) 𝑢(𝑣𝑤) = (𝑢𝑣)𝑤; 
2) 𝜆𝑢 = 𝑢𝜆 = 𝑢; 
3) |𝑢𝑣| = |𝑢| + |𝑣|; 
4) (𝑢𝑣)𝑅 = 𝑣𝑅𝑢𝑅; 
5) |𝑢𝑅| = |𝑢|. 
 
Seja Σ um alfabeto. 
Por Σ∗ designemos o conjunto de todas as palavras sobre Σ (incluíndo a palavra vazia 𝜆). Por Σ+ 
designemos o conjunto de todas as palavras não vazias sobre Σ. Então Σ+ = Σ∗ ∖ {𝜆}. 
Segundo o Teorema 2.1, o conjunto Σ∗ em relação à concatenação forma uma estrutura algébrica 
que se chama monóide (concretamente monóide livre gerado por Σ) e o conjunto Σ+ é um 
semigrupo livre gerado por Σ. Livre significa que qualquer palavra em Σ∗ (ou em Σ+) tem uma 
única forma como concatenação de símbolos em Σ. 
 
 
 Linguagens Formais e Autómatos 
12 
Definição 2.8. Seja 𝑤 uma palavra 
 
 
 
x chama-se prefixo de 𝑤; 
u chama-se sub-palavra de 𝑤; 
y chama-se sufixo de 𝑤. 
Vamos usar as designações seguintes: 
 𝑝𝑟𝑒𝑓(𝑤), 𝑝𝑟𝑒𝑓2(𝑤), 𝑠𝑢𝑏(𝑤), 𝑠𝑢𝑏1(𝑤), 𝑠𝑢𝑓(𝑤), 𝑠𝑢𝑓3(𝑤). 
 
Ordenação das palavras 
 
Seja ∑ um alfabeto totalmente ordenado Σ = {𝑎1, 𝑎2, … , 𝑎𝑛} e 𝑎1 < 𝑎2 < ⋯ < 𝑎𝑛. 
 
Ordem lexicográfica 
 
Se 𝑥, 𝑦 ∈ Σ∗ então 
𝑥 <𝐿 𝑦 ⇔ 𝑦 = 𝑥𝑣, 𝑣 ∈ Σ
+ 𝑜𝑢 ∃𝑢, 𝑣, 𝑤 ∈ Σ∗, 𝑎, 𝑏 ∈ Σ ∶ 𝑥 = 𝑢𝑎𝑣, 𝑦 = 𝑢𝑏𝑤 𝑜𝑛𝑑𝑒 𝑎 < 𝑏. 
Por exemplo, ver <𝐿 verdade <𝐿 verme. 
 
Ordem canónica 
 
Se 𝑥, 𝑦 ∈ Σ∗ então 
𝑥 <𝐶 𝑦 ⇔ |𝑥| < |𝑦| 𝑜𝑢 |𝑥| = |𝑦| 𝑒 𝑥 <𝐿 𝑦 
Por exemplo, ver <𝐶 verme <𝐶 verdade. 
x u y 
𝑤 
 Linguagens Formais e Autómatos 
13 
Σ0 = {𝜆} 
Σ2 na ordem 
lexicográfica 
Σ na ordem 
lexicográfica 
 
 
 
 
 
 
 
 
 
 
 
Exemplo 2.5. Ordem canónica das palavras binárias, (Σ = {0, 1}, 0 < 1) 
𝜆 <𝐶 0 <𝐶 1 <𝐶 00 <𝐶 01 <𝐶 10 <𝐶 11 <𝐶 000 <𝐶 … . 
Assim temos a sequência seguinte: 
𝜆, 0, 1, 00, 01, 10, 11, 000, … . 
Se para cada palavra 𝑤 desta sequência concatenamos 1 como prefixo 1𝑤 então recebemos: 
1, 10, 11, 100, 101, 110, 111, 1000, … . 
Esta sequência representa em binário os números 
1, 2, 3, 4, 5, 6, 7, 8, … 
das palavras binárias na ordem canónica. Assim, se não há confusão em vez da sequência das 
palavras na ordem canónica podemos escrever os seus números em decimal. 
Exemplo 2.6. a) Que número tem a palavra 𝑤 = 01011 na ordem canónica? 
 b) Que palavra binária tem o número 37 na ordem canónica? 
 
Resposta: a) 43 ; b) 𝑤37 = 00101. 
 Linguagens Formais e Autómatos 
14 
Definição 2.9. Dado um alfabeto Σ. Uma linguagem formal sobre Σ, ou simplesmente, 
linguagem, é um subconjunto 𝐿 de Σ∗ (𝐿 ⊆ Σ∗). 
Exemplo 2.7. 𝐿1 = ∅, 𝐿2 = {𝜆}, 𝐿3 = Σ, 𝐿4 = Σ
∗, 
Σ = {𝑎, 𝑏}, 𝐿5 = {𝑎
𝑛𝑏𝑛| 𝑛 ≥ 0}, 𝐿6 = {𝑎
𝑝| 𝑝 é 𝑝𝑟𝑖𝑚𝑜}, 𝐿7 = {𝜆, 𝑎, 𝑎𝑏𝑎}. 
Qualquer linguagem de programação é uma linguagem sobre o conjunto dos símbolos usados. 
 
Operações sobre linguagens 
 
Sejam 𝐿1, 𝐿2 e 𝐿 três linguagens sobre Σ. Definimos as seguintes operações com 𝐿1, 𝐿2 e 𝐿. 
1) União, 𝐿1 ⋃ 𝐿2 = {𝑤|𝑤 ∈ 𝐿1 𝑜𝑢 𝑤 ∈ 𝐿2}; 
2) Intersecção, 𝐿1 ∩ 𝐿2 = {𝑤|𝑤 ∈ 𝐿1 𝑒 𝑤 ∈ 𝐿2}; 
3) Diferença, 𝐿1 ∖ 𝐿2 = {𝑤|𝑤 ∈ 𝐿1 𝑒 𝑤 ∉ 𝐿2}; 
4) Complemento, �̅� = {𝑤|𝑤 ∈ Σ∗ ∖ 𝐿}; 
5) Concatenação, 𝐿1𝐿2 = {𝑢𝑣|𝑢 ∈ 𝐿1 , 𝑣 ∈ 𝐿2}; 
6) Potências, 𝐿0 = {𝜆}, 𝐿𝑛+1 = 𝐿𝑛𝐿, 𝑛 ≥ 0; 
7) Fecho de Kleene, 𝐿∗ = 𝐿0 ∪ 𝐿 ∪ 𝐿2 ∪ … ∪ 𝐿𝑛 ∪ … = ⋃ 𝐿𝑛𝑛≥0 ; 
8) Fecho positivo, 𝐿+ = 𝐿 ∪ 𝐿2 ∪ … ∪ 𝐿𝑛 ∪ … = ⋃ 𝐿𝑛𝑛≥1 ; 
9) Linguagem inversa, 𝐿𝑅 = {𝑤𝑅|𝑤 ∈ 𝐿}. 
 
Exemplo 2.8. Σ = {𝑎, 𝑏}, 𝐿1 = {𝜆, 𝑎, 𝑎𝑏}, 𝐿2 = {𝑏, 𝑏𝑏}. 
𝐿1𝐿2 = {𝑏, 𝑏𝑏, 𝑎𝑏, 𝑎𝑏𝑏, 𝑎𝑏𝑏𝑏}; 
𝐿2𝐿1 = {𝑏, 𝑏𝑏, 𝑏𝑎, 𝑏𝑏𝑎, 𝑏𝑎𝑏, 𝑏𝑏𝑎𝑏} (em geral 𝐿1𝐿2 ≠ 𝐿2𝐿1); 
 𝐿1
𝑅 = {𝜆, 𝑎, 𝑏𝑎}, 𝐿2
𝑅 = {𝑏, 𝑏𝑏}. 
 
 
 Linguagens Formais e Autómatos 
15 
Exemplo 2.9. Seja Σ um alfabeto. 
 Σ0 = {𝜆}; 
 Σ1 = Σ0Σ = {𝜆} Σ = Σ; 
 Σ2 = Σ1Σ = Σ Σ = {𝑤|𝑤 ∈ Σ∗ 𝑒 |𝑤| = 2}; 
 Σ3 = Σ2Σ = {𝑤|𝑤 ∈ Σ∗ 𝑒 |𝑤| = 3}; 
 ⋮ 
 Σ𝑛 = {𝑤|𝑤 ∈ Σ∗ 𝑒 |𝑤| = 𝑛}; 
 ⋮ 
 Σ∗ = {𝜆} ∪ Σ ∪ Σ2 ∪ … ∪ Σ𝑛 ∪ … = ⋃ Σ𝑛𝑛≥0 . 
 
Exemplo 2.10. {𝑎}∗ = {𝜆, 𝑎, 𝑎2, … , 𝑎𝑛, … }; 
{𝑎𝑏}∗ = {𝜆, 𝑎𝑏, (𝑎𝑏)2, … , (𝑎𝑏)𝑛, … }; 
∅∗ = {𝜆}; ∅+ = ∅; {𝜆}∗ = {𝜆}; {𝜆}+ = {𝜆}. 
𝜆, 𝑎𝑏,𝑐, 𝑎𝑏𝑎𝑏𝑐𝑐𝑐 ∈ {𝑎𝑏}∗{𝑐}∗; 
𝑎, 𝑎𝑏𝑐𝑎, 𝑎𝑐 ∉ {𝑎𝑏}∗{𝑐}∗. 
 
Teorema 2.2. Sejam 𝐿, 𝐿1, 𝐿2, 𝐿3 linguagens quaisquer 
1) 𝐿∅ = ∅𝐿 = ∅; 
2) {𝜆}𝐿 = 𝐿{𝜆} = 𝐿; 
3) (𝐿1 ∪ 𝐿2)𝐿3 = 𝐿1𝐿3 ∪ 𝐿2𝐿3; 
4) 𝐿1(𝐿2 ∪ 𝐿3) = 𝐿1𝐿2 ∪ 𝐿1𝐿3. 
As propriedades 3) e 4) generalizam-se a uma união infinita. 
 
 Linguagens Formais e Autómatos 
16 
Teorema 2.3. Seja 𝐿 uma linguagem. Então 
1) 𝜆 ∈ 𝐿+ ⇔ 𝜆 ∈ 𝐿; 
2) 𝐿+ = 𝐿𝐿∗ = 𝐿∗𝐿. 
Demonstração. 
1) (⇐) imediata pois 𝐿 ⊆ 𝐿+. 
(⇒)Suponhamos que 𝜆 ∈ 𝐿+. Então existe 𝑛 ≥ 1 tal que 𝜆 ∈ 𝐿𝑛. 
Logo, existem 𝑢1, 𝑢2, … , 𝑢𝑛 ∈ 𝐿 tais que 𝜆 = 𝑢1𝑢2 … 𝑢𝑛, donde |𝜆| = |𝑢1 … 𝑢𝑛| = |𝑢1| + ⋯ +
|𝑢𝑛| = 0 pelo que |𝑢𝑖| = 0 , 𝑖 = 1, 2, … , 𝑛. Assim, 𝑢𝑖 = 𝜆 , 𝑖 = 1, 2, … , 𝑛 e 𝜆 ∈ 𝐿. 
2) Temos 𝐿𝐿∗ = 𝐿(⋃ 𝐿𝑛𝑛≥0 ) = ⋃ (𝐿𝐿
𝑛)𝑛≥0 = ⋃ 𝐿
𝑛+1
𝑛≥0 = ⋃ 𝐿
𝑘
𝑘≥1 = 𝐿
+. 
𝐿∗𝐿 = 𝐿+ demonstra-se da mesma maneira. 
 
Problemas resolvidos 
 
2.1. Sejam Σ = {0, 1}, 𝐿1 = {10, 11}, 𝐿2 = {00, 1}. Achar 𝐿1 ∩ 𝐿2, 𝐿1 ∪ 𝐿2, 𝐿1𝐿2, 𝐿2𝐿1,
𝐿1
2, 𝐿1
𝑅. 
Solução. 𝐿1 ∩ 𝐿2 = ∅, 𝐿1 ∪ 𝐿2 = {10, 11, 00, 1}, 𝐿1𝐿2 = {1000, 101, 1100, 111}, 
𝐿2𝐿1 = {0010, 0011, 110, 111}, 𝐿1
2 = {1010, 1011, 1110, 1111}, 𝐿1
𝑅 = {01, 11}. 
 
2.2. Considera a palavra 𝑎𝑎𝑎𝑏𝑎 de alfabeto Σ = {𝑎, 𝑏}. Indica se tal palavra pertence ou não a 
cada uma das seguintes linguagens: 
a) {𝑎, 𝑏}∗; b) {𝑎𝑎𝑎, 𝑏𝑎𝑏} {𝑏𝑎, 𝑏𝑏}; c) {𝑎𝑎𝑎}∗ {𝑏}∗ {𝑎}; d) {𝑎}∗ {𝑏}∗ {𝑎}∗; 
e) {𝑎𝑎}∗ {𝑎}∗ {𝑎, 𝑏𝑎, 𝑏𝑏, 𝜆}. 
Solução. a) Sim ({𝑎, 𝑏}∗ − todas as palavras sobre {𝑎, 𝑏}); b) Sim; 
c) Sim 𝑎𝑎𝑎 ∈ {𝑎𝑎𝑎}∗ 𝑏 ∈ {𝑏}∗ 𝑎 ∈ {𝑎}; d) Sim 𝑎𝑎𝑎 ∈ {𝑎}∗ 𝑏 ∈ {𝑏}∗ 𝑎 ∈ {𝑎}; 
e) Sim 𝑎𝑎 ∈ {𝑎𝑎}∗ 𝑎 ∈ {𝑎}∗ 𝑏𝑎 ∈ {𝑎𝑎, 𝑏𝑎, 𝑏𝑏, 𝜆}. 
 Linguagens Formais e Autómatos 
17 
2.3. Para cada uma das seguintes afirmações sobre linguagens diz se é verdadeira ou falsa: 
a) 𝐿1𝐿2 = 𝐿2𝐿1; b) 𝐿∅ = ∅𝐿 = ∅; c) 𝐿
∗𝐿∗ = 𝐿∗; d) (𝐿1 ∪ 𝐿2)
∗ = 𝐿1
∗ ∪ 𝐿2
∗. 
Solução. a) Falso, 𝐿1 = {𝑎}, 𝐿2 = {𝑏} 𝐿1𝐿2 ≠ 𝐿2𝐿1; b) Verdadeiro; c) Verdadeiro; 
d) Falso, 𝐿1 = {𝑎}, 𝐿2 = {𝑏}. Então (𝐿1 ∪ 𝐿2)
∗ ≠ 𝐿1
∗ ∪ 𝐿2
∗. 
 
Problemas propostos 
 
2.4. Sejam Σ = {0, 1}, 𝐿1 = {00, 000}, 𝐿2 = {10, 110}. Achar 𝐿1 ∩ 𝐿2, 𝐿1𝐿2, 𝐿2𝐿1, 𝐿2
𝑅, 𝐿1
2, 
𝐿1
∗. 
2.5. Sejam 𝐿1, 𝐿2 duas linguagens sobre Σ. É verdadeiro ou falso que |𝐿1𝐿2| = |𝐿1| |𝐿2|? 
2.6. Seja Σ um alfabeto. Achar a cardinalidade de: 
a) Σ∗; b) Conjunto ℒ de todas as linguagens sobre Σ. 
2.7. Para cada uma das seguintes afirmações sobre linguagens diz se é verdadeira ou falsa: 
a) (𝐿∗)∗ = 𝐿∗; b) (𝐿1 ∩ 𝐿2)
∗ = 𝐿1
∗ ∩ 𝐿2
∗; c) (𝐿1𝐿2)
∗ = 𝐿1
∗𝐿2
∗; 
d) Se 𝐿1 ⊆ 𝐿2 então 𝐿1
∗ ⊆ 𝐿2
∗; e) Se 𝐿1 ⊂ 𝐿2 então 𝐿1
∗ ⊂ 𝐿2
∗. 
2.8. Seja Σ um alfabeto. Mostre que para quaisquer linguagens 𝐿1, 𝐿2, 𝐿3 ⊆ Σ
∗ 
a) 𝐿1(𝐿2 ∪ 𝐿3) = 𝐿1𝐿2 ∪ 𝐿1𝐿3; b) (𝐿1 ∪ 𝐿2)𝐿3 = 𝐿1𝐿3 ∪ 𝐿2𝐿3. 
2.9. Seja Σ um alfabeto. Mostre que para quaisquer linguagens 𝐿1, 𝐿2, 𝐿3 ⊆ Σ
∗ 
a) 𝐿1(𝐿2 ∩ 𝐿3) ⊆ 𝐿1𝐿2 ∩ 𝐿1𝐿3; b) (𝐿1 ∩ 𝐿2)𝐿3 ⊆ 𝐿1𝐿3 ∩ 𝐿2𝐿3. 
2.10.* Descreve informalmente a linguagem 𝐿 sobre Σ = {𝑎, 𝐴} definida recursivamente: 
(B): 𝐴 ∈ 𝐿; 
(PR): Se 𝑢 ∈ 𝐿 então 𝑎𝑢, 𝑢𝑎, 𝐴𝑢𝐴 ∈ 𝐿. 
 Linguagens Formais e Autómatos 
18 
2.11.* Demonstrar que 𝐿 = 𝐿∗ ⇔ 𝐿2 ⊆ 𝐿. 
(Nota: * significa exercício mais difícil) 
Respostas 
 
2.4. 𝐿1 ∩ 𝐿2 = {00, 000, 10, 110}; 𝐿1𝐿2 = {0010, 00110, 00010, 000110}; 
𝐿2𝐿1 = {1000, 10000, 11000, 110000}, 𝐿2
𝑅 = {01, 011}, 𝐿1
2 = {0000, 00000, 000000}, 
𝐿1
∗ = {𝜆, 00, 000, … , 0𝑛, … } = {𝜆} ∪ {0𝑛|𝑛 ≥ 2}. 
 
2.5. Em geral |𝐿1𝐿2| ≠ |𝐿1| |𝐿2| (Exemplo 2.8. |𝐿1| = 3, |𝐿2| = 2, |𝐿1𝐿2| = 5). 
 
2.6. a) |Σ∗| = ℵ0; b) |ℒ| = |𝑃(Σ
∗)| = ℂ. 
 
2.7. a) Verdadeiro. b) Falso (𝐿1 = {𝑎}, 𝐿2 = {𝑎𝑎}). c) Falso (𝐿1 = {𝑎}, 𝐿2 = {𝑎𝑎}). 
d) Verdadeiro. e) b) Falso (𝐿1 = ∅, 𝐿2 = {𝜆}). 
 
2.9. 𝐿1 = {𝑎, 𝑎𝑏}, 𝐿2 = {𝑏𝑐}, 𝐿3 = {𝑐}. 
𝐿1(𝐿2 ∩ 𝐿3) ⊂ 𝐿1𝐿2 ∩ 𝐿1𝐿3; 𝐿1(𝐿2 ∩ 𝐿3) = 𝐿1∅ = ∅; 𝐿1𝐿2 ∩ 𝐿1𝐿3 = {𝑎𝑏𝑐}. 
 
2.10. 𝐿 – todas as palavras sobre Σ = {𝑎, 𝐴} que tem um número ímpar de letras 𝐴. 
𝐿 = {𝑤|𝑤 ∈ {𝑎, 𝐴}∗ ∶ |𝑤|𝐴 é 𝑢𝑚 𝑛ú𝑚𝑒𝑟𝑜 í𝑚𝑝𝑎𝑟}. 
 
 Linguagens Formais e Autómatos 
19 
Capítulo 3 
 
Linguagens Regulares. Expressões Regulares 
 
Problema de representação finita de linguagens 
 
 Um problema que é muito importante na teoria de computação é o de representar 
linguagens, se possível por representações finitas, no sentido de uma representação ainda ser uma 
palavra sobre algum alfabeto Σ. 
 Obviamente, se se trata de uma linguagem finita o problema está resolvido, basta enumerar 
as suas palavras. Mas nem todas as linguagens são finitas. O conjunto de todas as palavras sobre 
Σ tem cardinalidade ℵ0 (|Σ
∗| = ℵ0). Por outro lado faz sentido exigir que linguagens diferentes 
tenham representações (palavras) diferentes. Mas a cardinalidade de todas as linguagens sobre Σ, 
é igual a ℂ (|𝑃(Σ∗)| = ℂ). Isto significa que nem todas as linguagens vão admitir uma tal 
representação finita. 
 Vamos neste capítulo especificar um método que descreva (representa) uma certa classe 
de linguagens que se chamam linguagens regulares. 
 
Linguagens Regulares (LR) 
 
Definição 3.1. Seja Σ um alfabeto 
(Base) ∅, {𝜆} e {𝑎} para cada 𝑎 ∈ Σ são linguagens regulares sobre Σ; 
(Passo Recursivo) Se 𝐿1, 𝐿2 são linguagens regulares sobre Σ então (𝐿1 ∪ 𝐿2), (𝐿1𝐿2) e (𝐿1)
∗ 
são linguagens regulares sobre Σ; 
(Fecho) As linguagens regulares são todas e apenas as obtidas por regras (Base) e (Passo 
Recursivo). 
 Linguagens Formais e Autómatos 
20 
Exemplo 3.1. Σ = {0, 1}. Mostrar que 𝐿 = {01, 110} é uma linguagem regular. 
Solução. 𝐿 = {01, 110} = {0} {1} ∪ ({1}{1}){0} pela Definição 3.1 é uma LR. 
Teorema 3.1. Qualquer linguagem finita 𝐿 é uma LR. 
Demonstração. Está claro que qualquer linguagem finita 𝐿 é união finita das concatenações 
finitas. Logo pela Definição 3.1 𝐿 é uma LR. 
Exemplo 3.2. Σ = {𝑎, 𝑏}. 
a) 𝐿1 − 𝑐𝑜𝑛𝑗𝑢𝑛𝑡𝑜 𝑑𝑒 𝑡𝑜𝑑𝑎𝑠 𝑎𝑠 𝑝𝑎𝑙𝑎𝑣𝑟𝑎𝑠 𝑠𝑜𝑏𝑟𝑒 Σ 𝑞𝑢𝑒 𝑐𝑜𝑛𝑡é𝑚 𝑠𝑢𝑏𝑝𝑎𝑙𝑎𝑣𝑟𝑎 "𝑏𝑏". 
b) 𝐿2 = {𝑎𝑏𝑤𝑏𝑎| 𝑤 ∈ 𝛴
∗}. 
Mostrar que 𝐿1 e 𝐿2 são LR’s. 
a) 𝐿1 = {𝑎, 𝑏}
∗{𝑏𝑏} {𝑎, 𝑏}∗; 
{𝑎, 𝑏}∗ = ({𝑎} ∪ {𝑏})∗ é uma LR (pela Definição 3.1); 
{𝑏𝑏} = {𝑏} {𝑏} é uma LR (pela Definição 3.1); 
b) TPC. 
 
Expressões Regulares (ER) 
 
Uma expressão regular é uma linguagem formal para definir uma representação finita das 
linguagens regulares. 
Definição 3.2. Seja Σ um alfabeto e Σ1 = Σ ∪ {∅, 𝜆, +,∙, 
∗, (, )}; 
(Base) ∅, 𝜆 e 𝑎 para cada 𝑎 ∈ Σ são expressões regulares sobre Σ1; 
(Passo Recursivo) Se 𝑟, 𝑠 são expressões regulares sobre Σ1 então (𝑟 + 𝑠), (𝑟𝑠) e (𝑟)
∗ são 
expressões regulares sobre Σ1; 
(Fecho) As expressões regulares são todas e apenas as obtidas por regras (Base) e (Passo 
Recursivo). 
 Linguagens Formais e Autómatos 
21 
Vamos retirar parêntesis, sempre que não haja ambiguidade considerando que “ ∗ ” precede “ ∙ ” e 
“ ∙ ” precede “+”. Omitiremos também o símbolo “ ∙ ”. Usaremos a notação 𝑟+ para representar a 
expressão regular 𝑟𝑟∗ ou 𝑟∗𝑟. 
Por exemplo, ER 0 + 10∗ significa (0 + (1 ⋅ ((0)∗))). 
Cada expressão regular 𝑟 vai representar uma linguagem regular 𝐿(𝑟). Basta interpretar os 
símbolos +, ∙ e ∗ como união, concatenação e fecho de Kleene. Com mais pormenores: 
𝐿(∅) = ∅; 
𝐿(𝜆) = {𝜆}; 
𝐿(𝑎) = {𝑎} para cada 𝑎 ∈ Σ; 
Se 𝑟 e 𝑠 são ER’s então 
𝐿(𝑟 + 𝑠) = 𝐿(𝑟) ∪ 𝐿(𝑠); 
𝐿(𝑟𝑠)= 𝐿(𝑟) 𝐿(𝑠); 
𝐿(𝑟∗) = 𝐿(𝑟)∗. 
Exemplo 3.3. Encontrar ER’s entre as palavras seguintes (Σ = {𝑎, 𝑏}): 
1) 𝑎; 
2) 𝑎 + 𝜆; 
3) 𝑎 +; 
4) 𝑎 + 𝑏𝑎∗; 
5) (𝑎 + 𝑏)∗; 
6) 𝑎) + ( ∗. 
Solução. 
1), 2), 4), 5) são ER’s; 
3), 6) não são ER’s. 
 
 Linguagens Formais e Autómatos 
22 
Exemplo 3.4. Achar a linguagem que representa a ER (𝑎 + 𝑏)∗𝑎. 
Solução. 
𝐿((𝑎 + 𝑏)∗𝑎) = 𝐿((𝑎 + 𝑏)∗) 𝐿(𝑎) = 𝐿(𝑎 + 𝑏)∗ 𝐿(𝑎) = (𝐿(𝑎) ∪ 𝐿(𝑏))
∗
𝐿(𝑎) =
({𝑎} ∪ {𝑏})∗{𝑎} = {𝑎, 𝑏}∗{𝑎} = {𝑤|𝑤 ∈ {𝑎, 𝑏}∗ 𝑒 𝑡𝑒𝑚 𝑠𝑢𝑓𝑖𝑥𝑜 𝑎}. 
 
Propriedades das ER’s 
 
Definição 3.3. Duas expressões regulares 𝑟 e 𝑠 são equivalentes se elas representam a mesma 
linguagem. Neste caso usamos a notação 𝑟 ≡ 𝑠. Assim, 
𝑟 ≡ 𝑠 ⇔ 𝐿(𝑟) = 𝐿(𝑠). 
Exemplo 3.5. Mostrar que se 𝑟 é uma ER, então 𝑟 ≡ 𝑟 + ∅ ≡ ∅ + 𝑟. 
Solução. 
𝐿(𝑟 + ∅) = 𝐿(𝑟) ∪ 𝐿(∅) = 𝐿(𝑟) ∪ ∅ = 𝐿(𝑟). 
Logo, 𝑟 ≡ 𝑟 + ∅ . Analogamente, 𝑟 ≡ ∅ + 𝑟. 
Teorema 3.2. (Propriedades das ER’s) 
Sejam 𝑟, 𝑠, 𝑡 ER’s. Então, 
1) (𝑟𝑠) 𝑡 ≡ 𝑟(𝑠𝑡); 
2) (𝑟 + 𝑠) + 𝑡 ≡ 𝑟 + (𝑠 + 𝑡); 
3) 𝑟 + 𝑠 ≡ 𝑠 + 𝑟; 
4) 𝑟 + 𝑟 ≡ 𝑟; 
5) 𝑟(𝑠 + 𝑡) ≡ 𝑟𝑠 + 𝑟𝑡; 
6) (𝑟 + 𝑠)𝑡 ≡ 𝑟𝑡 + 𝑠𝑡; 
7) 𝑟∅ ≡ ∅𝑟 ≡ ∅; 
8) 𝑟𝜆 ≡ 𝜆𝑟 ≡ 𝑟; 
9) (𝑟∗)∗ ≡ 𝑟∗; 
10) (𝜆 + 𝑟)∗ ≡ 𝑟∗; 
11) 𝑟∗ ≡ 𝜆 + 𝑟𝑟∗ ≡ 𝜆 + 𝑟+; 
 Linguagens Formais e Autómatos 
23 
12) (𝑟 + 𝑠)∗ ≡ (𝑟∗ + 𝑠∗)∗. 
Demonstração. 
7) 𝐿(𝑟∅) = 𝐿(𝑟) 𝐿(∅) = 𝐿(𝑟)∅ = ∅ = 𝐿(∅). 
9) 𝐿((𝑟∗)∗) = 𝐿(𝑟∗)∗ = (𝐿(𝑟∗))
∗
= (𝑝𝑟𝑜𝑏𝑙𝑒𝑚𝑎 2.7(𝑎)) = 𝐿(𝑟)∗ = 𝐿(𝑟∗). 
 
Problemas propostos 
 
3.1. Abreviar as parêntesis: 
ER Abreviação 
(𝒓 + 𝒔) 
((𝒓 + 𝒔) + 𝒕) 
((𝒓𝒔) 𝒕) 
((𝒓𝒔) + (𝒓𝒕)) 
((𝒓∗)∗) 
((𝟎∗)(𝟏𝟏)) 
(((𝟎∗)(𝟏𝟏)) + ((𝟏𝟎)𝟏)) 
(((𝟎 + 𝟏)∗) ((𝟎𝟎)𝟎)) + ((𝟎𝟏)∗(𝟎𝟏))) 
 
 
3.2. Achar a linguagem que representa cada ER. 
ER 𝑳(𝒓) 
0 + 1 
0∗ 
0∗11 
(0 + 1)∗ 
1∗0(0 + 1)∗ 
 Linguagens Formais e Autómatos 
24 
 
3.3. Achar ER’s que representam as linguagens seguintes: 
a) 𝐿 = {0, 01, 000}; 
b) 𝐿 = {000, 00000}∗; 
c) 𝐿 = {03𝑛+1| 𝑛 ≥ 0}; 
d) 𝐿 = { 𝑤|𝑤 ∈ {0, 1}∗ 𝑛ã𝑜 𝑡𝑒𝑚 1′𝑠 𝑒 𝑡𝑒𝑚 𝑢𝑚 𝑛ú𝑚𝑒𝑟𝑜 𝑝𝑎𝑟 𝑑𝑒 0′𝑠}; 
e) 𝐿 = {01𝑛0| 𝑛 ≥ 3}; 
f) 𝐿 = {𝑤|𝑤 é 𝑢𝑚 𝑛ú𝑚𝑒𝑟𝑜 𝑏𝑖𝑛á𝑟𝑖𝑜 𝑞𝑢𝑒 é 𝑝𝑜𝑡ê𝑛𝑐𝑖𝑎 𝑑𝑒 4}. 
 
Respostas 
3.1. 
ER Abreviação 
(𝑟 + 𝑠) 𝑟 + 𝑠 
((𝑟 + 𝑠) + 𝑡) 𝑟 + 𝑠 + 𝑡 
((𝑟𝑠) 𝑡) 𝑟𝑠𝑡 
((𝑟𝑠) + (𝑟𝑡)) 𝑟𝑠 + 𝑟𝑡 
((𝑟∗)∗) (𝑟∗)∗ 
((0∗)(11)) 0∗11 
(((0∗)(11)) + ((10)1)) 0∗11 + 101 
(((0 + 1)∗) ((00)0)) + (((01)∗(01))) (0 + 1)∗000 + (01)∗01 
 
3.2. 
ER 𝑳(𝒓) 
0 + 1 {0, 1} 
0∗ {𝜆, 0, … , 0𝑛, … } 
0∗11 {11, 011, … , 0𝑛11, … } 
(0 + 1)∗ {𝜆, 0, 1, 00, 01, 10, 11, 000, … } 
1∗0(0 + 1)∗ { 𝑤|𝑤 ∈ {0, 1}∗ 𝑒 𝑡𝑒𝑚 𝑎𝑙𝑔𝑢𝑚 0} 
 Linguagens Formais e Autómatos 
25 
 
3.3. 
a) 0 + 01 + 000. 
b) (000 + 00000)∗. 
c) 0(000)∗. 
d) (00)∗. 
e) 0(111)+0. 
f) 1(00)+. 
 
 Linguagens Formais e Autómatos 
26 
Capítulo 4 
 
Autómatos Finitos Determinísticos 
 
Um autómato finito deteminístico é um modelo matemático de um sistema cujo 
comportamento pode ser descrito como uma sequência determinista, discreta e linear de 
acontecimentos (estímulo - resposta) no tempo. 
Num dado momento o sistema encontra-se em alguma das suas configurações internas que 
são em número finito. Tais configurações, ditas estados, funcionam como memória sobre passos 
anteriores, e permitem determinar o comportamento do sistema para estímulos subsequentes. 
Considera-se que cada estímulo (símbolo de entrada) determina um e só um estado 
posterior, ou seja tem um efeito determinístico. O estado seguinte é uma função (no sentido 
matemático) do estado actual e do símbolo de entrada. 
 
 
 
 
 
 
Vamos dar a definição formal 
Definição 4.1. Um autómato finito determinístico (AFD) é um sistema de cinco elementos 
𝐴 = (𝑄, Σ, 𝛿, 𝐹, 𝑞0) onde: 
1) 𝑄 conjunto finito (não vazio) de estados; 
2) Σ alfabeto de entrada (input); 
3) 𝛿: 𝑄 × Σ → 𝑄 função de transição; 
4) 𝐹 ⊆ 𝑄 conjunto de estados finais (aceitadores); 
5) 𝑞0 ∈ 𝑄 estado inicial. 
 a . . . 
 Estados 
Cursor
 
Fita
 
Controlo Central
 
 Linguagens Formais e Autómatos 
27 
Exemplo 4.1. 𝐴 = (𝑄, Σ, 𝛿, 𝐹, 𝑞0) 
𝑄 = {𝑞0, 𝑞1, 𝑞2, 𝑞3}, Σ = {0,1}, 𝐹 = {𝑞1, 𝑞2}, 𝑞0 = 𝑞0. 
𝛿 0 1 
→ 𝑞0 𝑞1 𝑞3 
∗ 𝑞1 𝑞2 𝑞3 
∗ 𝑞2 𝑞2 𝑞2 
𝑞3 𝑞3 𝑞3 
 
Diagrama de transição de um AFD 
 
A um AFD fica associado um digrafo etiquetado: 
a) os vértices correspondem aos estados do autómato; 
b) a transição de estado 𝑞 para estado 𝑝 pelo símbolo de entrada 𝑎 corresponde um arco 
etiquetado por 𝑎 do vértice 𝑞 para o vértice 𝑝: 
 
 
 
c) Os estados finais são representados por duas circunferências: 
 
 
 
d) O estado inicial é apontado por uma seta: 
 
 
 
Este digrafo designa-se por diagrama de transição. 
 
𝑎 
𝑞 𝑝 𝛿(𝑞, 𝑎) = 𝑝 ⟹ 
𝑞 ∈ 𝐹 ⟹ 𝑞 
𝑞0 ⟹ 𝑞0 
 Linguagens Formais e Autómatos 
28 
Exemplo 4.2. Construir o diagrama de transição para o AFD 𝐴 do Exemplo 4.1. 
Solução. 
 
 
 
 
 
 
 
 
 
Caminho de computação 
 
Como a função de transição 𝛿 é bem-definida no conjunto 𝑄 × Σ, o diagrama de transição 
tem propriedade seguinte: para cada vértice (estado) 𝑞 e para cada letra (símbolo) de entrada 𝑎 
existe único arco com etiqueta 𝑎 que sai de 𝑞. 
Este implica que para cada palavra 𝑤 sobre Σ existe único caminho que começa em 𝑞0 e 
cujas etiquetas formam a palavra 𝑤. 
 Este caminho chama-se caminho de computação de palavra 𝑤 em autómato 𝐴 ou caminho 
que representa a palavra 𝑤 em autómato 𝐴. 
Exemplo 4.3. Achar caminho de computação de palavra 𝑤 em AFD 𝐴 do Exemplo 4.2. 
1) 𝑤 = 00 ; 2) 𝑤 = 011. 
Solução. 
1) 𝑤 = 00 
 
(𝑞0, 𝑞1, 𝑞2) − caminho de computação de 𝑤 = 00. 
0 0 
1 
𝑞0 
𝑞3 
𝑞2 𝑞1 
0,1 
0,1 
1 
0 
𝑞0 𝑞1 𝑞2 
0 
 Linguagens Formais e Autómatos 
29 
2) 𝑤 = 011 
 
 
 
(𝑞0, 𝑞1, 𝑞3, 𝑞3) − caminho de computação de 𝑤 = 011. 
 
Extensão da função de transição 
 
Definição 4.2. A extensão da função de transição 𝛿 de um AFD 𝐴 = (𝑄, Σ, 𝛿, 𝐹, 𝑞0) é a função 
𝛿: 𝑄 × Σ∗ → 𝑄 tal que 
1) 𝛿(𝑞, 𝜆) = 𝑞, 𝛿(𝑞, 𝑎) = 𝛿(𝑞, 𝑎), para todos 𝑞 ∈ 𝑄 e 𝑎 ∈ Σ; 
2) para todos 𝑤 ∈ Σ∗ e 𝑎 ∈ Σ, 𝛿(𝑞, 𝑤𝑎) = 𝛿(𝛿(𝑞, 𝑤), 𝑎). 
Exemplo 4.4. Achar 𝛿(𝑞0, 010) para AFD do Exemplo 4.2. 
Solução. 
𝛿(𝑞0, 010) = 𝛿(𝛿(𝑞0, 01), 0) = 𝛿(𝛿(𝛿(𝑞0, 0), 1), 0) = 𝛿(𝛿(𝛿(𝑞0, 0), 1), 0) = 
𝛿(𝛿(𝑞1, 1), 0) = 𝛿(𝑞3, 0) = 𝑞3. 
Nota 4.1. Para achar o resultado de 𝛿(𝑞, 𝑤) é preciso considerar o caminho no diagrama de 
transição do autómato que começa no estado 𝑞 e as etiquetas de arcos correspondem as letras de 
palavra 𝑤. 
Exemplo 4.5. Achar 𝛿(𝑞0, 010) para AFD do Exemplo 4.2 usando Nota 4.1. 
Solução. 
 
 
Logo 𝛿(𝑞0, 010) = 𝑞3. 
0 
𝑞0 𝑞1 𝑞3 
1 
𝑞3 
1 
0 
𝑞0 𝑞1 𝑞3 
1 
𝑞3 
0 
 Linguagens Formais e Autómatos 
30 
Linguagem reconhecida (aceite) por um AFD 
 
Definição 4.3. Diz-se que um AFD 𝐴 reconhece (aceita) uma palavra 𝒘 quando o caminho de 
computação de 𝑤 termina num estado final. 
 A linguagem aceite ou reconhecida pelo AFD 𝑨 é o conjunto de todas palavras em Σ∗ 
que são aceites pelo AFD 𝐴 o qual denotamos por 𝐿(𝐴). 
Mais formalmente. Seja 𝐴 = (𝑄, Σ, 𝛿, 𝐹, 𝑞0) um AFD. O conjunto de palavras𝐿(𝐴) = {𝑤 | 𝑤 ∈ Σ∗ 𝑒 𝛿(𝑞0, 𝑤) ∈ 𝐹} 
chama- se linguagem reconhecida (ou aceite) pelo 𝑨. Dizemos também que uma linguagem 𝑳 é 
aceite pelo autómato 𝑨 se e só se 𝐿 = 𝐿(𝐴). 
Definição 4.4. Diz-se que dois AFD’s 𝐴1 e 𝐴2 são equivalentes se e só se 𝐿(𝐴1) = 𝐿(𝐴2). Neste 
caso escrevemos que 𝐴1~𝐴2: 
𝐴1~𝐴2 ⟺ 𝐿(𝐴1) = 𝐿(𝐴2). 
 
Exemplo 4.6. Achar ER para 𝐿(𝐴) onde 𝐴 é o AFD do Exemplo 4.2. 
Solução. Se a palavra 𝑤 tem prefixo 1 ou 01 o autómato entra no estado 𝑞3 e nunca pode sair deste 
estado e não aceita 𝑤. Por outro lado, o autómato aceita 0 e todas as palavras 𝑤 que têm prefixo 
00. Assim, ER para 𝐿(𝐴) é 0 + 00(0 + 1)∗. 
Neste caso vamos escrever 𝐿(𝐴) = 0 + 00(0 + 1)∗. 
Existem dois tipos de problemas mais importantes ligados com autómatos e linguagens: 
1) para uma linguagem 𝐿 achar AFD 𝐴 (se existir) tal que 𝐿 = 𝐿(𝐴); 
2) para um AFD 𝐴 achar 𝐿(𝐴). 
 
Exemplo 4.7. Achar AFD 𝐴 tal que 𝐿(𝐴) = {𝜆}, Σ = {0,1}. 
 Linguagens Formais e Autómatos 
31 
Solução. 
 
 
 
Nota 4.2. Se 𝜆 ∈ 𝐿(𝐴) então o estado inicial 𝑞0 de 𝐴 deve ser final. 
 
Exemplo 4.8. Achar AFD 𝐴 tal que 𝐿(𝐴) = (0 + 1)∗, Σ = {0,1}. 
Solução. 
 
 
 
Exemplo 4.9. Achar AFD 𝐴 que aceite todas as palavras sobre alfabeto Σ = {0,1} que têm um 
número ímpar de letras 1. 
Solução. Este AFD tem dois estados 𝑞0 e 𝑞1 onde 𝑞0 significa que palavra de entrada tem um 
número par de 1’s e 𝑞1 significa que palavra de entrada tem um número ímpar de 1’s. Assim, 
 
 
 
 
 
 
Exemplo 4.10. (Prefixo) 
Achar AFD 𝐴 tal que 𝐿(𝐴) = 010(0 + 1)∗. 
Solução. Como 010 ∈ 𝐿(𝐴), o autómato deve ter um caminho de 𝑞0 para um estado final 
etiquetado por letras 0, 1, 0: 
 
𝑞1 𝑞0 
0,1 
0,1 
𝐴: 
𝑞0 
0,1 
𝐴: 
𝐴: 𝑞0 𝑞1 
1 0 0 
1 
 Linguagens Formais e Autómatos 
32 
 
 
Se aparecer outro prefixo, então deve existir um caminho para um novo estado que não é final e 
de onde o autómato não pode sair. Assim, 
 
 
 
 
 
 
 
 
 
Exemplo 4.11. (Subpalavra) 
Achar AFD 𝐴 tal que 𝐿(𝐴) = (0 + 1)∗110(0 + 1)∗. 
Solução. 
110 ∈ 𝐿(𝐴). Logo deve existir um caminho de 𝑞0 para um estado final etiquetado por letras 1, 1, 
0: 
 
 
 
Se o autómato entrou no 𝑞3 a palavra já tem 110 e pertence a 𝐿(𝐴) para qualquer sufixo. Assim, 
 
 
 
 
0 
𝑞0 𝑞1 𝑞3 
1 
𝑞2 
0 
0 
𝑞0 𝑞1 𝑞3 
1 
𝑞2 
0 
𝑞4 
0,1 
0 
0,1 
1 1 
𝐴: 
1 
𝑞0 𝑞1 𝑞3 
1 
𝑞2 
0 
1 
𝑞0 𝑞1 𝑞3 
1 
𝑞2 
0 
0,1 
 Linguagens Formais e Autómatos 
33 
Os estados do autómato tem os sentidos seguintes: 
𝑞0 − a palavra de entrada ainda não tem nenhuma parte (ou 𝜆) da subpalavra 110; 
𝑞1 − a palavra de entrada tem primeiro 1 da subpalavra 110; 
𝑞2 − a palavra de entrada tem 11 da subpalavra 110; 
𝑞3 − a palavra de entrada tem subpalavra 110. 
Agora se autómato fica no estado 𝑞0 e aparece letra 0, então a palavra de entrada continua com 
nenhuma parte de subpalavra 110 (ou 𝜆): 
 
 
 
 
Se o autómato fica no estado 𝑞1 e aparece letra 0, então a palavra de entrada tem sufixo 10 e não 
tem nenhuma parte de subpalavra 110 no sufixo (𝑞0). Logo, o autómato tem que ir para 𝑞0: 
 
 
 
 
 
Se o autómato fica no estado 𝑞2 e aparece letra 1, então a palavra de entrada tem sufixo 111 e 
tem a parte 11 de subpalavra 110. Logo o autómato continua a ficar em 𝑞2: 
 
 
 
 
 
É o nosso AFD 𝐴. 
1 
𝑞0 𝑞1 𝑞3 
1 
𝑞2 
0 
0,1 
0 
1 
𝑞0 𝑞1 𝑞3 
1 
𝑞2 
0 
0,1 
0 
0 
1 
𝑞0 𝑞1 𝑞3 
1 
𝑞2 
0 
0,1 
0 
0 
1 
𝐴: 
 Linguagens Formais e Autómatos 
34 
Exemplo 4.12. (Sufixo) 
Achar AFD 𝐴 tal que 𝐿(𝐴) = (0 + 1)∗101. 
Solução. 
101 ∈ 𝐿(𝐴). Logo deve existir um caminho de 𝑞0 para um estado final etiquetado por letras 1, 0, 
1: 
 
 
 
Os estados do autómato tem os sentidos seguintes: 
𝑞0 − a palavra de entrada ainda não tem nenhuma parte (ou 𝜆) do sufixo 101; 
𝑞1 − a palavra de entrada tem primeiro 1 do sufixo 101; 
𝑞2 − a palavra de entrada tem 10 da sufixo 101; 
𝑞3 − a palavra de entrada tem sufixo 101. 
Agora se autómato fica no estado 𝑞0 e aparece letra 0, então a palavra de entrada continua com 
nenhuma parte de sufixo 101 (ou 𝜆): 
 
 
 
 
Se o autómato fica no estado 𝑞1 e aparece letra 1, então a palavra de entrada tem sufixo 11 e tem 
primeiro 1 (𝑞1) de sufixo 101: 
 
 
 
 
 
1 
𝑞0 𝑞1 𝑞3 
0 
𝑞2 
1 
1 
𝑞0 𝑞1 𝑞3 
0 
𝑞2 
1 
0 
1 
𝑞0 𝑞1 𝑞3 
0 
𝑞2 
1 
1 0 
 Linguagens Formais e Autómatos 
35 
Se o autómato fica no estado 𝑞2 e aparece letra 0, então a palavra de entrada tem sufixo 100 e não 
tem nenhuma parte do sufixo 101 (𝑞0): 
 
 
 
 
 
 
Se o autómato fica no estado 𝑞3 e aparece letra 0, então a palavra de entrada tem sufixo 1010 e 
tem 10 do sufixo 101 (𝑞2): 
 
 
 
 
 
 
Se o autómato fica no estado 𝑞3 e aparece letra 1, então a palavra de entrada tem sufixo 1011 e 
tem primeiro 1 do sufixo 101 (𝑞1): 
 
 
 
 
 
 
É o nosso AFD 𝐴. 
 
 
 
1 
𝑞0 𝑞1 𝑞3 
0 
𝑞2 
1 
1 0 
0 
1 
𝑞0 𝑞1 𝑞3 
0 
𝑞2 
1 
1 0 
0 
0 
1 
𝑞0 𝑞1 𝑞3 
0 
𝑞2 
1 
1 0 
0 
0 
1 
𝐴: 
 Linguagens Formais e Autómatos 
36 
Teorema 4.1. Sejam 𝐴1 = (𝑄1, Σ, 𝛿1, 𝐹1, 𝑞0) e 𝐴2 = (𝑄2, Σ, 𝛿2, 𝐹2, 𝑝0) dois AFD’s. Então 
existem AFD’s 𝐴3, 𝐴4, 𝐴5, 𝐴6 tais que: 
a) 𝐿(𝐴3) = Σ
∗ ∖ 𝐿(𝐴1) = 𝐿(𝐴1)̅̅ ̅̅ ̅̅ ̅̅ ; 
b) 𝐿(𝐴4) = 𝐿(𝐴1) ∩ 𝐿(𝐴2); 
c) 𝐿(𝐴5) = 𝐿(𝐴2) ∖ 𝐿(𝐴1); 
d) 𝐿(𝐴6) = 𝐿(𝐴1) ∪ 𝐿(𝐴2). 
Demonstração. 
1) 𝐴3 = (𝑄1, Σ, 𝛿1, 𝑄1 ∖ 𝐹1, 𝑞0). É facil verificar que 𝐿(𝐴3) = 𝐿(𝐴1)̅̅ ̅̅ ̅̅ ̅̅ . 
2) 𝐴4 = (𝑄1 × 𝑄2, Σ, 𝛿, 𝐹1 × 𝐹2, (𝑞0, 𝑝0)) onde 𝛿 ((𝑞𝑖 , 𝑝𝑗), 𝑎) = (𝛿1(𝑞𝑖 , 𝑎), 𝛿2(𝑝𝑗 , 𝑎)), 
𝑞𝑖 ∈ 𝑄1, 𝑝𝑗 ∈ 𝑄2, 𝑎 ∈ Σ. 
3) 𝐿(𝐴5) = 𝐿(𝐴2) ∖ 𝐿(𝐴1) = 𝐿(𝐴2) ∩ (Σ
∗ ∖ 𝐿(𝐴1)) = 𝐿(𝐴2) ∩ 𝐿(𝐴1)̅̅ ̅̅ ̅̅ ̅̅ = 
𝐿(𝐴2) ∩ 𝐿(𝐴3). 
4) 𝐴4 = (𝑄1 × 𝑄2, Σ, 𝛿, (𝐹1 × 𝑄2) ∪ (𝑄1 × 𝐹2), (𝑞0, 𝑝0)) onde 𝛿 ((𝑞𝑖 , 𝑝𝑗), 𝑎) =
(𝛿1(𝑞𝑖 , 𝑎), 𝛿2(𝑝𝑗 , 𝑎)) , 𝑞𝑖 ∈ 𝑄1, 𝑝𝑗 ∈ 𝑄2, 𝑎 ∈ Σ. 
 
Problemas resolvidos 
 
4.1. Achar AFD 𝐴 que aceite todas as palavras sobre Σ = {0,1} que não têm sufixo 10. 
Solução. Vamos usar Teorema 4.1 (1). 
No inicio vamos construir AFD 𝐴1 tal que 𝐿(𝐴) = (0 + 1)
∗10. 
E depois AFD 𝐴: 𝐿(𝐴) = 𝐿(𝐴1)̅̅ ̅̅ ̅̅ ̅̅ . 
 
 
 
 
1 
𝑞0 𝑞1 𝑞2 
0 
1 0 
0 
1 
𝐴1: 
 Linguagens Formais e Autómatos 
37 
 
 
 
 
 
 
4.2. Achar AFD 𝐴 que aceite todas as palavras binárias que têm subpalavra 00 ou sufixo 01. 
 
Solução. No início vamos construir AFD’s 𝐴1 e 𝐴2 tais que 𝐿(𝐴1) = (0 + 1)
∗00(0 + 1)∗ e 
𝐿(𝐴2) = (0 + 1)
∗01. Depois, usando Teorema 4.1 (4), 𝐴: 
 
𝐿(𝐴) = (0 + 1)∗00(0 + 1)∗ + (0 + 1)∗01 ≡ (0 + 1)∗(00(0 + 1)∗ + 01). 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
1 
𝑞2 
0 
1 0 
0 
1 
𝐴: 𝑞1 𝑞0 
1 
𝑞0 𝑞1 𝑞2 
0 
1 
0 
0,1 
𝐴1: 
0 
𝑝0 𝑝1 𝑝2 
1 
0 1 
1 
0 
𝐴2: 
 Linguagens Formais e Autómatos 
38 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Simplificando, 
 
 
 
 
 
 
 
 
 
 
 
 
1 
𝑞0, 𝑝0 𝑞0, 𝑝1 𝑞0, 𝑝2 
1 
1 
0 
1 
𝑞1, 𝑝0 𝑞1, 𝑝1 
𝑞2, 𝑝2 𝑞2, 𝑝0 
𝑞1, 𝑝2 
𝑞2, 𝑝1 
1 
0 
1 
1 
0 
0 
0 
1 
1 
0 
0 
0 
0 
𝑞0, 𝑝0 𝑞0, 𝑝2 
1 
1𝐴: 
𝑞1, 𝑝1 
𝑞2, 𝑝2 𝑞2, 𝑝0 𝑞2, 𝑝1 
0 
1 
1 
0 
0 
1 
1 
0 
0 
0 
 Linguagens Formais e Autómatos 
39 
Também, podemos construir AFD 𝐴 só a partir do estado inicial (𝑞0, 𝑝0). 
 
 
 
 
 
 
 
 
 
 
 
4.3. Achar ER para 𝐿(𝐴) onde 
 
 
 
 
 
Solução. É claro que 0∗ ⊆ 𝐿(𝐴) e 𝑤 ∈ 𝐿(𝐴) sse o número de ocorrências de 1 é um múltiplo de 
4. Assim, 𝐿(𝐴) = 0∗(10∗10∗10∗10∗)∗. 
 
Problemas propostos 
 
4.4. Achar AFD 𝐴 tal que 𝐿(𝐴) = ∅, Σ = {0,1}. 
4.5. Achar AFD 𝐴 que aceite todas as palavras sobre Σ = {0,1} que têm um número par de 0’s. 
4.6. Achar AFD 𝐴 tal que 𝐿(𝐴) = {𝑏𝑛| 𝑛 ≥ 0}, Σ = {𝑎, 𝑏}. 
𝑞0, 𝑝0 
𝑞0, 𝑝2 
1 
1 
𝐴: 
𝑞1, 𝑝1 
𝑞2, 𝑝2 𝑞2, 𝑝0 
𝑞2, 𝑝1 
0 
1 
1 
0 
0 
1 
1 
0 0 
0 
1 
𝑞3 𝑞1 𝑞0 
1 
𝑞2 
1 
0 0 
1 
0 0 
𝐴: 
 Linguagens Formais e Autómatos 
40 
4.7. Achar AFD 𝐴 tal que 𝐿(𝐴) = (0 + 1)∗10101(0 + 1)∗. 
4.8. Achar AFD 𝐴 tal que 𝐿(𝐴) = (0 + 1)∗10101(0 + 1)∗̅̅ ̅̅ ̅̅ ̅̅ ̅̅ ̅̅ ̅̅ ̅̅ ̅̅ ̅̅ ̅̅ ̅̅ ̅̅ ̅̅ ̅̅ . 
4.9. 
a) Construir o diagrama de transição de AFD 𝐴; 
b) Achar os caminhos de computação para as palavras 
𝑤1 = 001, 𝑤2 = 101; 
c) Achar a linguagem 𝐿(𝐴). 
 
4.10. 
a) Construir o diagrama de transição de AFD 𝐴; 
b) Achar os caminhos de computação para as palavras 
𝑤1 = 001, 𝑤2 = 101; 
c) Achar a linguagem 𝐿(𝐴). 
 
4.11. Achar AFD 𝐴 que aceite todas as palavras binárias que têm um número par de 0’s e um 
número ímpar de 1’s. 
4.12. Construir um AFD 𝐴 que aceite todas as palavras sobre Σ = {𝑎, 𝑏} que: 
a) tem subpalavra “aa”; 
b) tem sufixo “ba”; 
c) não tem sufixo “ba”; 
d) tem subpalavra “aa” e sufixo “ba”. 
 
Respostas 
 
4.4. 
 
 𝛿 0 1 
 → 𝑞0 𝑞1 𝑞2 
𝐴: ∗ 𝑞1 𝑞1 𝑞1 
 𝑞2 𝑞2 𝑞2 
 𝛿 0 1 
 → 𝑞0 𝑞1 𝑞0 
𝐴: 𝑞1 𝑞2 𝑞0 
 ∗ 𝑞2 𝑞2 𝑞2 
𝑞0 
0,1 
𝐴: 𝑞1 
0,1 
 Linguagens Formais e Autómatos 
41 
4.5. 
 
 
 
 
4.6. 
 
 
 
 
 
4.7. 
 
 
 
 
 
 
 
4.8. 
 
 
 
 
 
 
 
 
𝑞0 
1 
𝐴: 𝑞1 
1 
0 
0 
𝑞0 
b 
𝐴: 𝑞1 
a,b 
a 
1 
𝑞0 𝑞1 𝑞5 
0 
𝑞2 
1 
1 
0 
0 
0 
1 𝐴: 𝑞3 𝑞4 
0 1 0,1 
1 
𝑞5 
0 1 
1 
0 
0 
0 
1 𝐴: 
0 1 0,1 
𝑞0 𝑞1 𝑞2 𝑞3 𝑞4 
 Linguagens Formais e Autómatos 
42 
4.9. 
a) 
 
 
 
 
 
b) 𝑤1 = 001, 
 ; 
 
 
 𝑤2 = 101, 
 . 
 
c) 𝐿(𝐴) = 0(0 + 1)∗. 
 
4.9. 
a) 
 
 
 
 
b) 𝑤1 = 001, 
 ; 
 
 
 𝑤2 = 101, 
 . 
c) 𝐿(𝐴) = (0 + 1)∗00(0 + 1)∗. 
0,1 
𝑞0 𝑞2 𝑞1 
1 
0 
0,1 
𝐴: 
0 
𝑞0 𝑞1 𝑞1 
0 
𝑞1 
1 
1 
𝑞0 𝑞2 𝑞2 
0 
𝑞2 
1 
0 
𝑞0 𝑞1 𝑞2 
0 
𝑞2 
1 
1 
𝑞0 𝑞0 𝑞1 
0 
𝑞0 
1 
1 
𝑞0 𝑞1 𝑞2 
0 
1 
0 
0,1 
𝐴: 
 Linguagens Formais e Autómatos 
43 
4.11. 
 
 
 
 
 
 
 
 
4.12. 
 a) 
 
 
 
 
 
 b) 
 
 
 
 
 
 
c) 
 
 
 
 
𝑞0, 𝑝0 
𝑞1, 𝑝0 
1 
1 
𝐴: 
𝑞1, 𝑝1 
𝑞0, 𝑝1 
0 
0 
1 
1 
0 0 
b 
𝑞0 𝑞1 𝑞2 
a 
b 
a 
a,b 
b 
𝑝2 
a 
b a 
a 
b 
𝑝1 𝑝0 
b 
𝑝2 
a 
b a 
a 
b 
𝑝1 𝑝0 
 Linguagens Formais e Autómatos 
44 
d) 
 
 
 
 
 
 
 
 
 
 
 
 
𝑞0, 𝑝0 
𝑞1, 𝑝0 
b 
a 
𝑞0, 𝑝1 
𝑞2, 𝑝1 𝑞2, 𝑝0 
𝑞1, 𝑝2 
b a 
a 
a 
a 
b 
b 
b 
a 
b 
𝑞2, 𝑝2 
a b 
 Linguagens Formais e Autómatos 
45 
Capítulo 5 
 
Autómatos Finitos Não Determinísticos com 𝝀 – arcos 
 
Definição 5.1. Um autómato finito não determinístico com 𝝀–arcos (AFND – 𝜆) é um sistema 
de cinco elementos 𝐴 = (𝑄, Σ, 𝛿, 𝐹, 𝑞0) onde: 
1) 𝑄 conjunto finito (não vazio) de estados; 
2) Σ alfabeto de entrada (input); 
3) 𝛿: 𝑄 × (Σ ∪ {𝜆}) → 𝑃(𝑄) função de transição; 
4) 𝐹 ⊆ 𝑄 conjunto de estados finais (aceitadores); 
5) 𝑞0 ∈ 𝑄 estado inicial. 
É claro que um AFD é um caso particular de AFND – 𝜆. 
Exemplo 5.1. 
 
 
 
 
 
 
 
 
 
 
Para uma palavra 𝑤 um AFND – 𝜆 pode ter mais que um (ou nenhum) caminho de computação. 
Por exemplo, 𝑤 = 01 AFND – 𝜆 do Exemplo 5.1. 
 
 
𝛿 0 1 𝜆 
→ 𝑞0 ∅ {𝑞0, 𝑞1} {𝑞1} 
𝑞1 {𝑞2} {𝑞1, 𝑞2} ∅ 
∗ 𝑞2 {𝑞2} ∅ {𝑞1} 
𝑞0 𝑞1 𝑞2 
0 
1 
1 
0 𝜆 1 1 
𝜆 
𝜆 
𝑞0 𝑞1 
0 
𝑞2 
1 𝜆 
𝑞1 𝑞1 
 Linguagens Formais e Autómatos 
46 
 
 
 
 
 
Assim, neste caso existem três caminhos diferentes. Também podemos dizer que existe árvore de 
computação: 
 
 
 
 
 
 
Definição 5.2. Diz-se que um AFND – 𝜆 𝐴 reconhece (ou aceita) uma palavra 𝑤 quando pelo 
menos um caminho de computação de 𝑤 termina num estado final (ou quando pelo menos uma 
folha da árvore de computação de 𝑤 pertence a 𝐹). 
 A linguagem aceite (ou reconhecida) pelo AFND – 𝜆 𝐴 é o conjunto de todas as palavras 
que são aceites pelo autómato, a qual denotamos por 𝐿(𝐴). 
Exemplo 5.2. Achar AFND – 𝜆 𝐴 tal que 𝐿(𝐴) = (0 + 1)∗010(0 + 1)∗. 
Solução. 
010 ∈ 𝐿(𝐴). Deve existir um caminho de computação desta palavra para um estado final 
 
 
 
 Se uma 𝑤 ∈ 𝐿(𝐴) então 𝑤 tem a forma onde 𝑢, 𝑣 ∈ {0, 1}∗. 
 
𝑤 = 𝑢 0 1 0 𝑣 
𝜆 
𝑞0 𝑞1 
0 
𝑞2 
1 𝜆 
𝑞1 𝑞2 
𝜆 
𝑞0 𝑞1 𝑞1 
0 
𝑞2 
𝜆 1 𝜆 
𝑞1 𝑞2 
𝜆 
𝑞0 𝑞1 𝑞1 
0 
𝑞2 
𝜆 1 𝜆 
𝑞1 𝑞2 
1 
𝑞1 
1 
𝑞2 
0 
𝑞0 𝑞1 𝑞3 
1 
𝑞2 
0 
 Linguagens Formais e Autómatos 
47 
Assim, 
 
 
 
 
 
O autómato vai ler prefixo 𝑢 no estado 𝑞0 depois o autómato vai passar para 𝑞3 por 010 e vai 
terminar em 𝑞3. Logo, 𝑤 ∈ 𝐿(𝐴). 
Se a palavra 𝑤 não tem subpalavra 010 o autómato nunca pode passar de 𝑞0 para 𝑞3 e 𝑤 ∉ 𝐿(𝐴). 
Então, 𝐿(𝐴) = (0 + 1)∗010(0 + 1)∗. 
Consideremos por exemplo, a árvore de computação para palavra 𝑤1 = 01010 ∈ 𝐿(𝐴). 
 
 
 
 
 
 
 
 
Se 𝑤2 = 011 ∉ 𝐿(𝐴) 
 
 
 
 
 
 
 
0 
𝑞0 𝑞1 𝑞3 
1 
𝑞2 
0 
0,1 
0,1 
𝐴: 
0 
𝑞3 
𝑞3 
0 
𝑞0 
0 1 
𝑞3 𝑞3 
1 
𝑞2 
𝑞0 𝑞0 
0 
𝑞0 
1 0 
𝑞0 𝑞1 
0 𝑞0 
1 
𝑞1 
𝑞2 
0 
1 0 
0 
1 
𝑞2 
𝑞0 
1 
𝑞0 
𝑞0 
0 𝑞0 
1 
𝑞1 
 Linguagens Formais e Autómatos 
48 
Exemplo 5.3. (Único estado final) 
Solução. 
 
 
 
 
 
 
AFND – 𝜆 𝐴1 tem único estado final e 𝐿(𝐴1) = 𝐿(𝐴). 
 
Exemplo 5.4. (União) 
Solução. 
 
 
 
 
 
 
 
Então, 𝐿(𝐴) = 𝐿(𝐴1) ∪ 𝐿(𝐴2). 
 
Exemplo 5.5. Construir AFND – 𝜆 𝐴 tal que 𝐿(𝐴) = 01(0 + 1)∗ + (0 + 1)∗11. 
Solução. 
 
 
 
 
 
 𝐿(𝐴1) = 01(0 + 1)
∗. 
𝜆 
𝜆 
𝐴 
𝐴1 
𝜆 
𝜆 
𝐴 
𝐴1 
𝐴2 
𝑞0 𝑞1 𝑞2 
1 0 
0,1 
𝐴1: 
 Linguagens Formais e Autómatos 
49 
 
 
 
 
 𝐿(𝐴2) = (0 + 1)
∗11. 
 
 
 
 
 
 
 
 
 
 
𝐿(𝐴) = 01(0 + 1)∗ + (0 + 1)∗11. 
 
Exemplo 5.6. (Concatenação) 
Sejam 𝐴1 e 𝐴2 dois AFND – 𝜆‘s e 𝐴1 tem único estado final (Exemplo 5.3). 
Construir AFND – 𝜆 𝐴 tal que 𝐿(𝐴) = 𝐿(𝐴1)𝐿(𝐴2). 
Solução. 
 
 
 
 
 
Então, 𝐿(𝐴) = 𝐿(𝐴1)𝐿(𝐴2). 
𝑝0 𝑝1 𝑝2 
1 1 
0,1 
𝐴2: 
𝑝0 𝑝1 𝑝2 
1 1 
0,1 
𝑞0 𝑞1 𝑞2 
1 0 
0,1 
𝐴: 𝑠0 
𝜆 
𝜆 
𝜆 
𝐴 
𝐴1 𝐴2 
 Linguagens Formaise Autómatos 
50 
Exemplo 5.7. (Fecho positivo) 
Seja 𝐴1 um AFND – 𝜆 que tem único estado final. Construir AFND – 𝜆 𝐴 tal que 𝐿(𝐴) = 𝐿(𝐴1)
+. 
Solução. 
 
 
 
 
 
𝐿(𝐴) = 𝐿(𝐴1)
+. 
 
Exemplo 5.8. (Fecho de Kleene) 
Seja 𝐴1 um AFND – 𝜆 com único estado final. Construir AFND – 𝜆 𝐴 tal que 𝐿(𝐴) = 𝐿(𝐴1)
∗. 
Solução. 
 
 
 
 
 
 
𝐿(𝐴) = 𝐿(𝐴1)
∗. 
Exemplo 5.9. (Linguagem inversa) 
 
 
 
 
 
Construir AFND – 𝜆 𝐴 tal que 𝐿(𝐴) = 𝐿(𝐴1)
𝑅. 
𝜆 
𝐴 
𝐴1 
𝜆 
𝜆 
𝐴 
𝐴1 
𝜆 
𝜆 
b 
𝑞2 
a 
b 
a 
b 
a 
𝑞1 𝑞0 𝐴1: 
 Linguagens Formais e Autómatos 
51 
Solução. 
 
 
 
 
 
𝐿(𝐴) = 𝐿(𝐴1)
𝑅. 
Nota 5.1. (Linguagem inversa) 
Seja 𝐴1 um AFND – 𝜆 com único estado final. Para construir AFND – 𝜆 𝐴 tal que 𝐿(𝐴) = 𝐿(𝐴1)
𝑅 
é preciso: 
1) trocar estado inicial com estado final; 
2) mudar o sentido de todos os arcos pelo sentido contrário. 
 
Exemplo 5.10. Construir AFND – 𝜆 𝐴 tal que 𝐿(𝐴) = ((01(0 + 1)∗ + (0 + 1)∗10)𝑅)∗. 
Solução. 
 
 
 
 
 
 𝐿(𝐴1) = 01(0 + 1)
∗. 
 
 
 
 
 𝐿(𝐴2) = (0 + 1)
∗10. 
 
 
b 
𝑞2 
a 
b 
a 
b 
a 
𝑞1 𝑞0 𝐴: 
𝑞0 𝑞1 𝑞2 
1 0 
0,1 
𝐴1: 
𝑝0 𝑝1 𝑝2 
0 1 
0,1 
𝐴2: 
 Linguagens Formais e Autómatos 
52 
 
 
 
 
 
 
 
 
 
𝐿(𝐴3) = 01(0 + 1)
∗ + (0 + 1)∗10. 
 
 
 
 
 
 
 
 
𝐿(𝐴4) = 01(0 + 1)
∗ + (0 + 1)∗10 e 𝐴4 tem único estado final. 
 
 
 
 
 
 
 
 
 
𝐿(𝐴5) = (01(0 + 1)
∗ + (0 + 1)∗10)𝑅. 
𝑝0 𝑝1 𝑝2 
0 1 
0,1 
𝑞0 𝑞1 𝑞2 
1 0 
0,1 
𝐴3: 𝑠0 
𝜆 
𝜆 
𝑝0 𝑝1 𝑝2 
0 1 
0,1 
𝑞0 𝑞1 𝑞2 
1 0 
0,1 
𝐴4: 
𝜆 
𝜆 
𝑠0 𝑡0 
𝜆 
𝜆 
𝑝0 𝑝1 𝑝2 
0 1 
0,1 
𝑞0 𝑞1 𝑞2 
1 0 
0,1 
𝐴5: 
𝜆 
𝜆 
𝑠0 𝑡0 
𝜆 
𝜆 
 Linguagens Formais e Autómatos 
53 
 
 
 
 
 
 
 
 
 
 
 
𝐿(𝐴) = ((01(0 + 1)∗ + (0 + 1)∗10)𝑅)∗. 
 
 
 
𝝀 – Fecho 
 
Definição 5.3. Seja 𝐴 = (𝑄, Σ, 𝛿, 𝐹, 𝑞0) um AFND – 𝜆 e 𝐸 ⊆ 𝑄, 
𝐹𝑒𝑐ℎ𝑜𝜆(𝐸) = {𝑝|𝑝 ∈ 𝐸 𝑜𝑢 ∃𝑞1, 𝑞2, … , 𝑞𝑘: 𝑞1 ∈ 𝐸, 𝑞𝑘 = 𝑝, 𝑞𝑖+1 ∈ 𝛿(𝑞𝑖 , 𝜆), 𝑖=1, 2, … , 𝑘 − 1}. 
 
Então, 𝐹𝑒𝑐ℎ𝑜𝜆(𝐸) dá nos o conjunto de estados em que o autómato está ou pode vir a estar sem 
consumir qualquer símbolo a partir de 𝐸. 
 
 
 
 
 
Exemplo 5.11. Seja 𝐴 do Exemplo 5.1. Achar 𝐹𝑒𝑐ℎ𝑜𝜆({𝑞0}), 𝐹𝑒𝑐ℎ𝑜𝜆({𝑞1}), 𝐹𝑒𝑐ℎ𝑜𝜆({𝑞2}). 
𝐹𝑒𝑐ℎ𝑜𝜆(𝐸) 
 
 
𝜆 𝐸 
 𝜆 
𝜆 
𝜆 
𝑝0 𝑝1 𝑝2 
0 1 
0,1 
𝑞0 𝑞1 𝑞2 
1 0 
0,1 
𝐴: 
𝜆 
𝜆 
𝑠0 𝑡0 𝑢0 𝑤0 
𝜆 𝜆 
𝜆 
𝜆 
𝜆 
𝜆 
 Linguagens Formais e Autómatos 
54 
Solução. 
 
 
 
 
 
 
 
 
 
 
Simulação de um AFND – 𝝀 por um AFD 
 
Teorema 5.1. Qualquer linguagem 𝐿 que seja aceite por algum AFND – 𝜆 𝐴1 é aceite por algum 
AFD 𝐴2 e vice-versa. 
 Seja 𝐴 = (𝑄, Σ, 𝛿, 𝐹, 𝑞0) um AFND – 𝜆 
Vamos estender 𝛿 para o domínio 𝑃(𝑄) × (Σ ∪ {𝜆}). Esta nova função designemos por 𝛿′. 
Definição 5.4. Seja 𝐴 = (𝑄, Σ, 𝛿, 𝐹, 𝑞0) um AFND – 𝜆 e 𝐸 ⊆ 𝑄 
𝛿′(𝐸, 𝑎) = 𝐹𝑒𝑐ℎ𝑜𝜆 ( ⋃ 𝛿(𝑞, 𝑎)
𝑞∈ 𝐹𝑒𝑐ℎ𝑜𝜆(𝐸)
) 
𝛿′(∅, 𝑎) = ∅ 𝑝𝑎𝑟𝑎 𝑡𝑜𝑑𝑜 𝑎 ∈ Σ. 
 
 
 
 
𝑞0 
 
 
𝑞1 
𝜆 
𝑞1 
𝑞2 
 
 
𝑞1 
𝜆 
𝐹𝑒𝑐ℎ𝑜𝜆({𝑞0}) = {𝑞0, 𝑞1} 
𝐹𝑒𝑐ℎ𝑜𝜆({𝑞1}) = {𝑞1} 
𝐹𝑒𝑐ℎ𝑜𝜆({𝑞2}) = {𝑞1, 𝑞2}. 
𝐹𝑒𝑐ℎ𝑜𝜆(𝐸) 
 
 
𝜆 
𝛿′(𝐸, 𝑎) 
 
 
𝜆 
𝜆 
𝜆 
𝑎 
𝑎 
𝑎 
 Linguagens Formais e Autómatos 
55 
Exemplo 5.12. Seja 𝐴 do Exemplo 5.1. Achar 𝛿′({𝑞0}, 0) e 𝛿
′({𝑞1, 𝑞2}, 1). 
 
 
 
 
 
 
 
 
 
 
 
 
 
Algoritmo 5.1. (Construção de um AFD 𝐴2 que é equivalente a um AFND – 𝜆 𝐴1 dado) 
Input: AFND – 𝜆 𝐴1 = (𝑄, Σ, 𝛿, 𝐹, 𝑞0), a função 𝛿
′. 
Output: AFD 𝐴2 tal que 𝐿(𝐴2) = 𝐿(𝐴1). 
1. 𝑄′ ≔ 𝐹𝑒𝑐ℎ𝑜𝜆({𝑞0}) //estado inicial 
2. repeat 
2.1. if existe vértice 𝑋 ∈ 𝑄′ e símbolo 𝑎 ∈ Σ e não há arco que sai de 𝑋 com etiqueta 𝑎 then 
2.1.1. 𝑌 ≔ 𝛿′(𝑋, 𝑎) 
2.1.2. if 𝑌 ∉ 𝑄′ then 𝑄′ ≔ 𝑄′ ∪ 𝑌 
2.1.3. acrescente o arco de 𝑋 em 𝑌 etiquetado por 𝑎 
else 𝑑𝑜𝑛𝑒 ≔ 𝑡𝑟𝑢𝑒 
 until done 
3. estados finais de AFD 𝐴2 é 𝐹
′ = {𝑋 ∈ 𝑄′|𝑋 ∩ 𝐹 ≠ ∅} 
Assim, AFD 𝐴2 = (𝑄′, Σ, 𝛿′, 𝐹′, 𝐹𝑒𝑐ℎ𝑜𝜆({𝑞0})) e 𝐿(𝐴2) = 𝐿(𝐴1). 
𝑞0 
𝑞1 
𝜆 
0 
𝑞2 
 
𝑞1 
𝜆 
𝛿′({𝑞0}, 0) = {𝑞1, 𝑞2} 𝛿
′ = ({𝑞0}, 0) 
𝑞2 
𝑞1 
1 
𝑞2 
 
𝑞1 
𝜆 
𝛿′({𝑞1, 𝑞2}, 1) = {𝑞1, 𝑞2} 𝛿
′ = ({𝑞1, 𝑞2}, 1) 
 Linguagens Formais e Autómatos 
56 
Exemplo 5.13. Construir AFD 𝐴2 que é equivalente a um AFND – 𝜆 𝐴1 (𝐿(𝐴2) = 𝐿(𝐴1)). 
 
 
 
 
 
 
 
 
 
Solução. 𝐹𝑒𝑐ℎ𝑜𝜆({𝑞0}) = {𝑞0, 𝑞2} 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
b 
𝑞2 
a 
a,b 
a 
b 
𝜆 
𝑞1 𝑞0 
𝐴1: 
a,b 
𝑞2 
 
 
𝑞0 
𝑎 
𝑞2 
𝑞1 
𝜆 
𝑞0 
𝑎 
𝑎 
𝑎 
𝑞2 
 
 
𝑞0 𝑞1 
𝑏 
𝑏 
𝑞1 
 
 𝑏 
𝑞2 
𝑞1 
𝜆 
𝑞0 
𝑏 
𝑞2 
 
 
𝑞0 𝑎 
𝑞2 
𝑞1 
𝜆 
𝑞0 
𝑎 
𝑎 
𝑎 
𝑞1 
𝑞2 
 
 
𝑞0 𝑏 
𝑞2 
𝑞0 
𝜆 
𝑞1 
𝑏 
𝑏 
𝑏 
𝑞1 
𝑞1 
 Linguagens Formais e Autómatos 
57 
 
 
 
 
 
 
 
 
 
 
 
 
 
Problemas resolvidos 
 
5.1. 
 
 
 
 
 
 
 
 Quais das seguintes palavras são aceites por 𝐴: 𝜆, aa, aba, abba, bba, abab. 
Solução. 𝜆 ∈ 𝐿(𝐴), 𝑞0 é final. 
 
𝑎𝑎 ∉ 𝐿(𝐴) 
 
𝑎𝑏𝑎 ∈ 𝐿(𝐴) 
𝛿′ 𝑎 𝑏 
→ 𝐴 = {𝑞0, 𝑞2} {𝑞0, 𝑞1, 𝑞2} = 𝐵 {𝑞1} = 𝐶 
∗ 𝐵 = {𝑞0, 𝑞1, 𝑞2} {𝑞0, 𝑞1, 𝑞2} = 𝐵 {𝑞0, 𝑞1, 𝑞2} = 𝐵 
∗ 𝐶 = {𝑞1} ∅ = 𝐷 {𝑞0, 𝑞1, 𝑞2} = 𝐵 
𝐷 = ∅ ∅ = 𝐷 ∅ = 𝐷 
a b 
a,b 
b 
a 𝐴2: 
a,b 
𝐴 𝐵 𝐶 𝐷 
a 
b 
𝜆 
b 
b 
𝐴: 
a 
b 
𝑞0 𝑞1 𝑞2 
𝑞4 𝑞3 
𝜆 
𝑞0 𝑞1 
a 
𝑞1 
𝜆 
𝑞0 𝑞1 
a 
𝑞4 
a b 
𝑞3 𝑞0 
 Linguagens Formais e Autómatos 
58 
 
𝑎𝑏𝑏𝑎 ∉ 𝐿(𝐴) 
 
 
 
 
𝑏𝑏𝑎 ∉ 𝐿(𝐴) 
 
𝑎𝑏𝑎𝑏 ∈ 𝐿(𝐴) 
 
 
5.2. Construir AFND – 𝜆 𝐴 tal que 𝐿(𝐴) = (01)∗. 
Solução. 
 
 
 
 
 
 𝐿(𝐴1) = 01 
 
 
 
 
 
 
 
𝐿(𝐴) = (01)∗ 
 
 
 
a 
𝑞0 𝑞1 
b 
𝑞2 
𝜆 
b 
b 
𝑞4 
𝑞0 
𝑞3 
b 
𝑞4 
𝜆 
𝑞0 𝑞1 𝑞4 
a 
𝑞4 
𝜆 b 
𝑞0 𝑞1 
a 
𝑞0 
b 
𝑞0 𝑞1 𝑞2 
1 0 𝐴1: 
𝜆 
𝑞0 𝑞1 𝑞2 
1 0 
𝐴: 
𝜆 
𝜆 𝜆 
𝑝0 𝑞3 
 Linguagens Formais e Autómatos 
59 
5.3. 
 
 
 
 
 
 
 
 
Construir AFND – 𝜆 𝐴1 tal que 𝐿(𝐴1) = 𝐿(𝐴)
𝑅. 
Solução. 
 
 
 
 
 
 
 
 
 
 
 
 
 
𝐿(𝐴1) = 𝐿(𝐴)
𝑅 
 
 
 
b 
b 
a 
b 
b 
𝐴: 
a a 
𝑞0 𝑞1 
𝑞3 𝑞2 
a 
b 
b 
a 
b 
b 
𝐴2: 
a a 
𝑞0 𝑞1 
𝑞4 
𝑞3 𝑞2 
a 
𝜆 𝜆 
b 
b 
a 
b 
b 
𝐴1: 
a a 
𝑞0 𝑞1 
𝑞4 
𝑞3 𝑞2 
a 
𝜆 𝜆 
 Linguagens Formais e Autómatos 
60 
Problemas propostos 
 
5.4. 
 
 
 
 
 
 
 
 
 Quais das seguintes palavras são aceites por 𝐴: 𝜆, aa, aba, abba, bba, abab. 
 
5.5. Constrói um AFND – 𝜆 que aceite todas as palavras binárias com 1 na terceira posição a 
contar do fim. 
 
5.6. 
 
 
 
 
 
 
Construir AFND – 𝜆 𝐴1 tal que 𝐿(𝐴1) = 𝐿(𝐴)
𝑅. 
 
5.7.b 
𝜆 
b 
b 
𝐴: 
a 
b 
𝑞0 𝑞1 𝑞2 
𝑞3 𝑞4 
b 
𝑞2 
a 
b 
a 
a 
b 
𝑞1 𝑞0 𝐴: 
a b 
a,b,c 
𝐴: b 𝑞0 𝑞1 𝑞2 𝑞3 
 Linguagens Formais e Autómatos 
61 
a) Achar 𝐿(𝐴). 
b) Achar AFD equivalente. 
c) Por quê é que a linguagem reconhecida pelo autómato 𝐴1 não é complementar da 
linguagem 𝐿(𝐴)? 
 
 
 
 
𝐿(𝐴1) ≠ 𝐿(𝐴)̅̅ ̅̅ ̅̅ . 
 
5.8. 
 
 
 
 
 
 
 
Construir AFD 𝐴2 que é equivalente a AFND – 𝜆 𝐴1. 
 
 
5.9. 
 
 
 
 
 
 
 
Construir AFD 𝐴2 que é equivalente a AFND – 𝜆 𝐴1. 
𝛿 0 1 𝜆 
→ 𝑞0 {𝑞0} {𝑞0, 𝑞2} {𝑞1} 
𝑞1 {𝑞5} {𝑞2} ∅ 
𝑞2 {𝑞3} ∅ ∅ 
∗ 𝑞3 ∅ ∅ {𝑞4} 
∗ 𝑞4 {𝑞3} ∅ ∅ 
𝑞5 ∅ {𝑞4} ∅ 
a b 
a,b,c 
𝐴1: b 𝑞0 𝑞1 𝑞2 𝑞3 
𝐴1: 
a 
b 
𝜆 
b 
𝐴1: 
𝜆 a 
𝑞0 𝑞1 
𝑞3 𝑞2 
 Linguagens Formais e Autómatos 
62 
Respostas 
 
5.4. 𝑏𝑏𝑎 ∈ 𝐿(𝐴). 
 
5.5. 
 
 
 
 
5.6. 
 
 
 
 
 
 
5.7. 
a) 𝐿(𝐴) = (𝑎 + 𝑏 + 𝑐)∗𝑎𝑏(𝜆 + 𝑏). 
 
b) 
 
 
 
 
 
 
𝛿′ 𝑎 𝑏 𝑐 
→ {𝑞0} {𝑞0, 𝑞1} {𝑞0} {𝑞0} 
{𝑞0, 𝑞1} {𝑞0, 𝑞1} {𝑞0, 𝑞2} {𝑞0} 
∗ {𝑞0, 𝑞2} {𝑞0, 𝑞1} {𝑞0, 𝑞3} {𝑞0} 
∗ {𝑞0, 𝑞3} {𝑞0, 𝑞1} {𝑞0} {𝑞0} 
1 0,1 
0,1 
0,1 
𝑞0 𝑞1 𝑞2 𝑞3 
b 
𝑞2 
a 
b 
a 
a 
b 
𝑞1 𝑞0 𝐴1: 
 Linguagens Formais e Autómatos 
63 
5.8. 
 
 
 
 
 
 
 
 
5.9. 
 
 
 
 
 
 
 
 
 
 
 
𝛿′ 0 1 
→ {𝑞0, 𝑞1} {𝑞0, 𝑞1, 𝑞5} {𝑞0, 𝑞1, 𝑞2} 
{𝑞0, 𝑞1, 𝑞5} {𝑞0, 𝑞1, 𝑞5} {𝑞0, 𝑞1, 𝑞2, 𝑞4} 
{𝑞0, 𝑞1, 𝑞2} {𝑞0, 𝑞1, 𝑞3, 𝑞4, 𝑞5} {𝑞0, 𝑞1, 𝑞2} 
{𝑞0, 𝑞1, 𝑞2, 𝑞4} {𝑞0, 𝑞1, 𝑞3, 𝑞4, 𝑞5} {𝑞0, 𝑞1, 𝑞2} 
{𝑞0, 𝑞1, 𝑞3, 𝑞4, 𝑞5} {𝑞0, 𝑞1, 𝑞3, 𝑞4, 𝑞5} {𝑞0, 𝑞1, 𝑞2, 𝑞4} 
𝐴2: 
a 
a,b 
b 
a,b 
𝐴2: a,b 
𝑞0, 𝑞2, 𝑞3 𝑞1 
∅ 𝑞3 
 Linguagens Formais e Autómatos 
64 
Capítulo 6 
 
Autómatos Finitos e Expressões Regulares 
 
Exemplo 6.1. 
 
 
 
 
 
Achar ER para linguagem 𝐿(𝐴). 
Solução. Para achar ER que representa 𝐿(𝐴) vamos usar o método de eliminação de estados. Se 
eliminar 𝑞1 então deve se substituir o caminho (𝑞0, 𝑞1, 𝑞0) por um laço em 𝑞0 etiquetado por bb 
e o caminho (𝑞0, 𝑞1, 𝑞2) por um arco de 𝑞0 para 𝑞2 etiquetado por ba: 
 
 
 
 
 
 
Obtem-se o diagrama seguinte: 
 
 
 
 
 
 
ou 
b a 
a 
b a 
b 
𝐴: 
a b 
𝑞0 𝑞1 𝑞2 𝑞3 
b a 
bb 
a 
b 
ba 
a 
b 
a b 
𝑞0 𝑞1 𝑞2 𝑞3 
ba b 
bb 
a 
a 
a b 
𝑞0 𝑞2 𝑞3 
 Linguagens Formais e Autómatos 
65 
 
 
 
 
 
 
Vamos eliminar 𝑞2: 
 
 
 
 
 
 
 
 
Assim, 
 
 
 
 
 
 
Então, obtemos ER 
(𝑎 + 𝑏𝑏)∗𝑏𝑎𝑎∗𝑏 (𝑏 + 𝑎𝑎∗𝑏)∗ 
que representa a linguagem 𝐿(𝐴) das palavras que levam o autómato dado do estado 𝑞0 ao estado 
𝑞3. Substuindo 𝑎𝑎
∗ ≡ 𝑎+ recebemos 
(𝑎 + 𝑏𝑏)∗𝑏𝑎+𝑏 (𝑏 + 𝑎+𝑏)∗. 
 
ba b 
a 
a 
a+bb b 
𝑞0 𝑞2 𝑞3 
ba b 
a 
aa*b 
baa*b 
a 
a+bb b 
𝑞0 𝑞2 𝑞3 
baa*b 
a+bb b+aa*b 
𝑞0 𝑞3 
 Linguagens Formais e Autómatos 
66 
Algoritmo de eliminação de estados 
 
1. Verificar se o autómato dado tem estados que não sejam acessíveis do estado inicial. Se tiver, 
retirá-los bem como os arcos que tenham origem ou fim nesses estados. 
2. Proceder de modo análogo a (1) para eliminar todos os estados que não permitam chegar a 
algum dos estados finais. 
3. Se depois de ter efectuado (1) e (2) já não existirem estados finais, então dar como resultado a 
ER ∅. 
4. Se depois de ter efectuado (1) e (2) ainda existir algum estado final, então introduzir um novo 
estado que passa ser o único estado final. 
5. Eliminar sucessivamente cada um dos estados do autómato obtido em (4) com excepção do 
estado inicial e do estado final. 
 
Nota 6.1. Depois de cada passo simplificar os arcos paralelos: 
 
 
 
 
 
 
 
O diagrama final depois da aplicação do algoritmo pode ter um estado ou dois estados. 
 
 
Se então ER é 𝑎∗. 
 
 
Se então ER é 𝑎∗𝑏 (𝑐 + 𝑑𝑎∗𝑏)∗. 
 
b 
a 
a+b 
a,b a+b 
c 
b 
d 
a 
a 
 Linguagens Formais e Autómatos 
67 
Teorema 6.1. (Teorema de Kleene) 
Seja 𝐿 uma linguagem formal. As afirmações seguintes são equivalentes: 
1) 𝐿 é uma linguagem regular. 
2) Existe um AFND – 𝜆 𝐴1 tal que 𝐿 = 𝐿(𝐴1). 
3) Existe um AFD 𝐴2 tal que 𝐿 = 𝐿(𝐴2). 
Demonstração. 1) ⇒ 2). Realmente, se 𝐿 é linguagem regular então existe expressão regular 𝑟 
que representa 𝐿. O digrafo desta expressão regular 𝐺(𝑟) (Tema de auto-aprendizagem) é 
AFND – 𝜆 𝐴1 tal que 𝐿 = 𝐿(𝐴1). 
2) ⇒ 3). Pelo Teorema 5.1. (Capítulo 5), se existe AFND – 𝜆 𝐴1 tal que 𝐿 = 𝐿(𝐴1) então existe 
um AFD 𝐴2 tal que 𝐿 = 𝐿(𝐴2). 
3) ⇒ 1). Se existe AFD 𝐴2 tal que 𝐿 = 𝐿(𝐴2) então existe expressão regular que representa 
𝐿(𝐴2) = 𝐿 (Algorítmo de eliminação de estados). Assim 𝐿 é linguagem regular. 
 
Problemas resolvidos 
 
6.1. Achar ER 𝑟 que representa a linguagem 𝐿(𝐴) onde 𝐴 é o autómato seguinte: 
 
 
 
 
 
 
 
 
 
 
1 
1 
0,1 
0 
1 
0 
𝐴: 
0,1 
𝑞0 𝑞1 𝑞2 𝑞3 
𝑞4 
 Linguagens Formais e Autómatos 
68 
Solução. Realizando passos 1 e 2 do algoritmo recebemos: 
 
 
 
 
 
 
Depois de passos 3 e 4 recebemos: 
 
 
 
 
 
 
 
 
 
 
Começamos o passo 5, vamos eliminar 𝑞1: 
 
 
 
 
 
 
 
 
 
 
1 
1 
1 
0 
𝑞0 𝑞1 𝑞2 𝑞3 
1 
1 
𝜆 𝜆 
1 
0 
𝜆 
𝑞0 𝑞1 𝑞2 𝑞3 
𝑞4 
1 
1 
𝜆 𝜆 
1 
0 
11 
𝜆 
𝑞0 𝑞1 𝑞2 𝑞3 
𝑞4 
11 
 Linguagens Formais e Autómatos 
69 
 
 
 
 
 
 
 
 
 
Eliminamos 𝑞3: 
 
 
 
 
 
 
 
 
 
Eliminamos 𝑞2: 
 
 
 
 
 
 
 
 
11 0 
𝜆 
𝜆 𝜆 
𝑞0 𝑞2 𝑞3 
𝑞4 
11 
11 0 
𝜆 
𝜆 
0𝜆=0 
0 
𝜆 
𝑞0 𝑞2 𝑞3 
𝑞4 
11 
𝜆+(11)+( 𝜆+0) 
𝑞0 𝑞4 
11 
𝜆+0 
𝜆 
𝑞0 𝑞2 
𝑞4 
11 
11(11)*( 𝜆+0) 
11 
𝜆+0 𝜆 
𝑞0 𝑞2 
𝑞4 
11 
 Linguagens Formais e Autómatos 
70 
Assim, ER 𝑟 que representa 𝐿(𝐴) é 
𝑟 = 𝜆 + (11)+(𝜆 + 0). 
 
6.2. Achar ER 𝑟 que representa a linguagem 𝐿(𝐴) onde 𝐴 é o autómato seguinte: 
 
 
 
 
 
 
 
 
 
Solução. Depois de passos 1,2,3 e 4 recebemos: 
 
 
 
 
 
 
 
 
 
 
 
 
Começamos o passo 5, vamos eliminar 𝑞1: 
 
1 1 
0,1 
1 
0 
0 𝐴: 
0 
𝑞0 𝑞1 
𝑞2 
𝑞5 
𝑞4 𝑞3 
𝜆 
𝜆 
1 1 
0+1 
1 
0 
0 
0 
𝑞0 𝑞1 
𝑞2 
𝑞5 
𝑞4 𝑞3 
𝜆 
𝜆 
𝑞6 
𝜆 𝜆 
 Linguagens Formais e Autómatos 
71 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Eliminamos 𝑞2: 
 
 
 
 
 
 
 
 
 
1 1 
0+1 
1 
0 
0 
0 
𝑞0 𝑞1 
𝑞2 
𝑞5 
𝑞4 𝑞3 
𝜆 
𝜆 
𝑞6 
𝜆 𝜆 
0 
1 𝜆1≡1, 1+1≡1, 𝜆0≡0 
0+1 
0 
0 
0 
𝑞0 𝑞5 
𝑞2 
𝑞4 
𝑞6 𝑞3 
1 
𝜆 
𝜆 
𝜆 
1 
0+1 
10 
0 
0 
0 
𝑞0 𝑞5 
𝑞2 
𝑞4 
𝑞6 𝑞3 
1 
𝜆 
𝜆 
𝜆 
1 
 Linguagens Formais e Autómatos 
72 
 
 
 
 
 
 
 
 
 
Eliminamos 𝑞5: 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Eliminamos𝑞3: 
0+1 
0 
0 
𝑞0 𝑞5 
𝑞3 
𝑞4 
𝑞6 
1 
𝜆 
𝜆 
𝜆 
10 
0+1 
0 
0 
𝑞0 𝑞5 
𝑞3 
𝑞4 
𝑞6 
1 
𝜆 
𝜆 
𝜆 
01 
10 
0+1 
0 
01 
𝑞0 𝑞4 
𝑞3 𝑞6 
𝜆 
𝜆 
𝜆 
10 
 Linguagens Formais e Autómatos 
73 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Eliminamos 𝑞4: 
 
 
 
 
 
 
 
 
 
10 
0+1 
10 
0 
01 
𝑞0 𝑞4 
𝑞3 𝑞6 
0 𝜆 
𝜆 
𝜆 
0 
10 
0𝜆≡0, 10𝜆≡10 
0+1 
01+10 
𝑞0 𝑞4 
𝑞6 
𝜆+0 
0 
10 
0+1 
01+10 
𝑞0 𝑞4 
𝑞6 
𝜆+0 (01+10)0*(𝜆+0) 
0 
10 
 Linguagens Formais e Autómatos 
74 
 
 
 
 
Assim, ER 𝑟 que representa 𝐿(𝐴) é 
𝑟 = (0 + 1)∗(10 + (01 + 10)0∗(𝜆 + 0)). 
 
6.3. Seja 𝐿 a linguagem de todas as palavras binárias com um número par de letras “0”. 
Achar ER 𝑟 que representa 𝐿. 
Solução. 
No inicio vamos construir um autómato 𝐴 tal que 𝐿(𝐴) = 𝐿: 
 
 
 
 
 
Agora vamos achar ER 𝑟 que representa 𝐿(𝐴): 
Eliminamos 𝑞1: 
 
 
 
 
 
 
 
Assim, ER 𝑟 que representa 𝐿(𝐴) = 𝐿 é 
𝑟 = (1 + 01∗0)∗. 
0+1 
𝑞0 𝑞6 
10+(01+10)0*(𝜆+0) 
𝑞0 
1 
𝐴: 𝑞1 
1 
0 
0 
01*0 
𝑞0 
1 
𝑞1 
1 
0 
0 
𝑞0 
1+01*0 
 Linguagens Formais e Autómatos 
75 
Problemas propostos 
 
6.4. Seja 𝐿 a linguagem de todas as palavras binárias com um número ímpar de letras “0”. 
Achar ER 𝑟 que representa 𝐿. 
 
6.5. 
 
 
 
 
 
 
a) Achar AFD 𝐴1 tal que 𝐿(𝐴) = 𝐿(𝐴1). 
b) Achar ER 𝑟 que representa 𝐿(𝐴). 
c) Achar ER 𝑟 que representa 𝐿(𝐴1). 
 
 
6.6. 
 
 
 
 
 
 
a) Achar AFD 𝐴1 tal que 𝐿(𝐴) = 𝐿(𝐴1). 
b) Achar ER 𝑟 que representa 𝐿(𝐴1). 
 
𝛿 0 1 𝜆 
→ 𝑞0 {𝑞0, 𝑞1} ∅ {𝑞3} 
𝑞1 ∅ {𝑞2} {𝑞0} 
∗ 𝑞2 {𝑞2} {𝑞2} ∅ 
∗ 𝑞3 {𝑞0, 𝑞1} ∅ ∅ 
a 
b 
𝜆 
b 
𝐴: 
𝜆 a 
𝑞0 𝑞1 
𝑞3 𝑞2 
𝐴: 
 Linguagens Formais e Autómatos 
76 
6.7. 
 
 
 
 
 
 
 
a) Achar AFD 𝐴1 tal que 𝐿(𝐴) = 𝐿(𝐴1). 
b) Achar ER 𝑟 que representa 𝐿(𝐴). 
 
6.8. Utilizando o Teorema de Kleene e os resultados dos Capítulos 4 e 5, demonstrar que: 
a) A intersecção de duas linguagens regulares é regular. 
b) A linguagem inversa de uma linguagem regular é regular. 
c) A linguagem complementar de uma linguagem regular é regular. 
Respostas 
 
6.4. 𝑟 = 1∗0 (1 + 01∗0)∗. 
 
6.5. a) 
 
 
 
 
 
b) 𝑟 = 𝜆 + (𝑎 + 𝑏)𝑏∗𝑎. 
c) 𝑟 = 𝜆 + (𝑎 + 𝑏)𝑏∗𝑎. 
𝛿′ 𝑎 𝑏 
→ ∗ {𝑞0, 𝑞2, 𝑞3} {𝑞1} {𝑞1} 
{𝑞1} {𝑞3} {𝑞1} 
∗ {𝑞3} ∅ ∅ 
∅ ∅ ∅ 
a 
b 
𝜆 
b 
𝐴: 
𝜆 
𝜆 
1 2 
4 3 
a 
𝐴1: 
 Linguagens Formais e Autómatos 
77 
6.6. a) 
 
 
 
 
 
 
 
b) 𝑟 = 𝜆 + 0(0 + 1)∗. 
 
6.7. a) 
 
 
 
 
 
 
 
 
 
b) 𝑟 = (𝑎𝑏∗ + 𝜆) 𝑎∗(𝑏 + 𝜆). 
 
1 0,1 
1 
0,1 
𝐴1: 
0 
𝑞0, 𝑞3 𝑞0, 𝑞1, 𝑞3 
∅ 
𝑞2 
0 
a 
a 
b 
b 
𝐴1: b a 
1,3,4 2,3,4 
3,4 4 
a,b 
a,b 
∅