Buscar

Notas de Aula - Parte 1

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você viu 3, do total de 38 páginas

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você viu 6, do total de 38 páginas

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você viu 9, do total de 38 páginas

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Prévia do material em texto

Linguagens Formais
Notas de Aula
Conteúdo
1 Introdução 2
2 Conceitos Básicos 2
3 Gramáticas 4
3.1 Linguagem Gerada por uma Gramática . . . . . . . . . . . . . . . . . 5
3.2 Tipos de Gramáticas . . . . . . . . . . . . . . . . . . . . . . . . . . 5
3.3 Classificação de Linguagens . . . . . . . . . . . . . . . . . . . . . . 6
4 Autômatos Finitos 8
4.1 Autômatos Finitos Determinísticos . . . . . . . . . . . . . . . . . . . 8
4.2 Palavra aceita por um AFD . . . . . . . . . . . . . . . . . . . . . . . 10
4.3 Autômatos Finitos Não-Determinísticos . . . . . . . . . . . . . . . . 12
4.4 Palavra aceita por um AFN . . . . . . . . . . . . . . . . . . . . . . . 13
4.5 Equivalência de AFNs e AFDs . . . . . . . . . . . . . . . . . . . . . 16
4.6 Autômatos Finitos com Transições Vazias - AFNε . . . . . . . . . . . 19
4.7 Equivalência entre AFNε e AFD . . . . . . . . . . . . . . . . . . . . 21
4.8 Equivalência entre AFNε e GR . . . . . . . . . . . . . . . . . . . . . 24
4.9 Minimização de Autômatos Finitos . . . . . . . . . . . . . . . . . . . 28
5 Expressões Regulares 31
5.1 Leis Algébricas para ER’s . . . . . . . . . . . . . . . . . . . . . . . 32
5.2 Equivalência de ERs e AFNεs . . . . . . . . . . . . . . . . . . . . . 34
1
1 Introdução
Linguagem é um meio de comunicação usado por indivíduos de uma comunidade. É
composta por: palavras e regras gramaticais.
Um linguagem é dita formal quando pode ser representada por um sistema mate-
mático. É definida por: sintaxe (estrutura) e semântica (significado)
2 Conceitos Básicos
Alfabeto (ou vocabulário): conjunto finito de símbolos
Exemplos:
Σ1 = {a, b, c, . . . , z}
Σ2 = {0, 1}
Σ3 = {x|x ∈ N ∧ x ≤ 9}
Palavra (ou string ou sentença): sequência finita de símbolos provenientes de um
alfabeto.
Exemplos: palavras sobre o alfabeto Σ2: 001 e 10001.
Tamanho (ou comprimento) de uma palavra: número de símbolos que compõem
a palavra.
Exemplo: palavra w = abb tem tamanho |w| = 3
Palavra vazia - ε: palavra que não contém nenhum símbolo. Tamanho |ε| = 0
Potências de um alfabeto: Σk é o conjunto de palavras de tamanho k sobre o voca-
bulário Σ
Exemplos: considere o vocabulário Σ = {0, 1}:
Σ0 = {ε}
Σ1 = {0, 1}
Σ2 = {00, 01, 10, 11}
Quantas palavras tem o conjunto Σ3?
Σ∗ é o conjunto de todas as palavras compostas por símbolos de Σ, isto é,
Σ∗ = Σ0 ∪ Σ1 ∪ Σ2 ∪ . . ..
Exemplo: Σ∗ = {ε, 0, 1, 00, 11, 01, 10, 000, . . .}
Σ+ = Σ∗ − {ε}
Concatenação: se v e w são palavras, vw é a concatenação de v e w.
Exemplos: considere v = abc e w = xyz
vw = abcxyz
wv = xyzabc
εw = wε = w
2
Prefixo: sequência inicial de símbolos de uma palavra.
Exemplos: considere a palavra abcb. São prefixos desta palavra: ε, a, ab, abc, abcb
Sufixo: sequência final de símbolos de uma palavra.
Exemplos: considere a palavra abcb. São sufixos desta palavra: ε, b, cb, bcb, abcb
Subpalavra: qualquer sequência contínua de símbolos de uma palavra.
Exemplos: considere a palavra abcb. São subpalavras palavra: todos os prefixos e
sufixos, bc, c
Reverso de uma palavra: se u ∈ Sigma∗, uR é o reverso de u, definido por:
uR =
{
ε, se u = ε;
awR, se u = wa, onde w ∈ Σ∗ e a ∈ Σ.
Exemplos: considere a palavra v = abcbb, então vR = bbcba.
Linguagem: qualquer conjunto de palavras sobre um alfabeto, ou seja, L é uma lin-
guagem sobre um alfabeto V , se L ⊆ V ∗. Podem ser finitas, infinitas ou vazia.
Exemplos:
• Conjunto das palavras da Língua Portuguesa;
• Conjunto dos programas válidos em C;
• Conjunto das palavras formadas por n 0’s, seguidos por n 1’s: {ε, 01, 0011, . . .};
• Conjunto das palavras com o mesmo número de 0’s e 1’s: {ε, 0101, 01, 0110,
1100, . . .}.
Linguagem vazia: ∅ (não possui nenhuma palavra).
Linguagem contendo somente a palavra vazia: {ε}.
OBS.: ∅ 6= {ε}
Representação:
• Listar as palavras (para linguagens finitas);
• Descrição algébrica. Ex.: {anbncn|n ≥ 1};
• Definir um algoritmo que determine se uma palavra pertence ou não a uma lin-
guagem (reconhecedor). Ex.: autômatos finitos;
• Definir um mecanismo que gera todas as palavras da linguagem (geração). Ex.:
gramáticas
3
3 Gramáticas
É um formalismo usado para gerar o subconjunto de palavras sobre um alfabeto que
faz parte de uma linguagem. Permitem descrever linguagens infinitas de forma finita.
Definição 3.1 (Gramáticas) Uma gramática G é definida por:
G = (N,T, P, S),
onde
- N é o conjunto de variáveis;
- T é o conjunto de símbolos terminais, tal que N ∩ T = ∅;
- P = {α → β|α ∈ V ∗NV ∗ ∧ β ∈ V ∗} é o conjunto de regras de produção,
onde V = N ∪ T ;
- S ∈ N é a variável inicial da gramática.
Exemplo: gramática que gera os números inteiros não negativos:
G = (N,T, P, I),
onde
N = {I,D};
T = {0, 1, . . . , 9};
P = {I → D|DI,D → 0|1| . . . |9}.
Esta gramática gera sentenças do tipo 00, 0012, . . .
Como podemos alterá-la para evitar 0’s à esquerda?
Como usar essas regras para produzir o natural 150?
I ⇒ DX ⇒ 1X ⇒ 1BX ⇒ 1DX ⇒ 15X ⇒ 15B ⇒ 150
Cada aplicação de regra realizada para produzir o número 150 é denominada derivação.
Definição 3.2 (Derivações) Uma derivação, denotada por⇒, é a operação de subs-
tituição realizada de acordo com as regras da gramática. Sequências de zero ou mais
derivações são denotadas por⇒∗ e sequências de uma ou mais derivações são deno-
tadas por⇒+.
Exemplos: considerando a sequência de derivações acima (para gerar o numeral 150),
temos: S ⇒∗ 150, S ⇒∗ S, S ⇒+ 150, S 6⇒+ S.
Exercícios 3.1
4
1. Considere a seguinte gramática:
({S,A,B}, {0, 1}, {S → AB,A→ 0|AB,B → 1|1B}, S)
(a) Que linguagem é descrita por essa gramática?
(b) Descreva duas derivações diferentes para produzir a seguinte palavra:
0111
Palavra de uma linguagem: sequência de terminais obtida a partir do símbolo inicial
da gramática que gera tal linguagem, através de derivações sucessivas.
Exemplos: considerando a gramática G, definida acima, temos as seguintes palavras
na linguagem gerada por G: 0, 1, 10, 120, . . .
Forma sentencial: sequência de terminais e variáveis obtida a partir do símbolo ini-
cial da gramática, através de derivações sucessivas.
Exemplos: considerando a gramática G, definida acima, temos as seguintes formas
sentenciais: DX, 1BX, 15B, . . .
3.1 Linguagem Gerada por uma Gramática
É o conjunto de todas as palavras de uma linguagem obtidas de uma gramática por
derivações sucessivas a partir do símbolo inicial.
Definição 3.3 (Linguagem gerada por uma gramática) Dada uma gramática G =
(N,T, P, S), a linguagem gerada por G é definida por:
L(G) = {w|w ∈ T ∗ ∧ S ⇒∗ w}
Exercícios 3.2
1. Qual a linguagem gerada pela gramática a seguir?
G = ({S}, {0, 1}, S → 0S1|01, S)
3.2 Tipos de Gramáticas
As gramáticas podem ser classificadas de acordo com características de suas regras de
produção:
Irrestritas - GI (tipo 0): regras do tipo α→ β, tal que α ∈ V ∗NV ∗ e β ∈ V ∗;
5
Sensíveis ao Contexto - GSC (tipo 1): regras do tipo α → β, tal que |α| ≤ |β|.
OBS.: Não são possíveis regras do tipo S → ε;
Livre de Contexto - GLC (tipo 2): regras do tipo α→ β, tal que α ∈ N e β ∈ V ∗;
Regulares - GR (tipo 3): regras do tipo α → vβ (ou α → βv), tal que α ∈ N ,
β ∈ N ∪ {ε} e v ∈ T ∗.
Pode-se estender uma gramática incluindo regras do tipo S → ε, porém a variável S
não poderá aparecer do lado direito de nenhuma regra.
Exemplo:
Considere a gramática a seguir:
G = ({S,C,B}, {a, b, c}, P, S), onde
P = {S → aSBC|aBC,CB → BC, aB → ab, bB → bb, bC → bc, cC → cc}
L(G) = {abc, aabbcc, aaabbbccc, . . .}
Podemos estendê-la para incluir a palavra vazia como segue:
G′ = ({S′, S, C,B}, {a, b, c}, P ∪ {S′ → ε|S}, S′)
L(G′) = {ε, abc, aabbcc, aaabbbccc, . . .}
3.3 Classificação de Linguagens
As linguagens podem ser classificadas de acordo com as gramáticas que as geram.
Recursivamente Enumeráveis - LRE: linguagens geradas por GIs;
Sensíveis ao Contexto - LSC:linguagens geradas por GSCs adicionando-se a palavra
vazia. Para isso estende-se as gramáticas incluindo regras do tipo S → ε;
Livre de Contexto - LLC: linguagens geradas por GLCs;
Regulares - LR: linguagens geradas por GRs.
Chomsky organizou essas linguagens em uma hierarquia ilustrada na Figura 1.
6
Figura 1: Hierarquia de Chomsky.
Exercícios 3.3
1. Construa uma gramática G tal que:
(a) L(G) = {anbm|n ≥ 0 ∧m ≥ 1}
(b) L(G) = {aibjci|i ≥ 0 ∧ j ≥ 1}
2. Construa umaGR tal que: L(G) = {w|w ∈ {0, 1}+ e na˜o possui 1′s consecutivos}
3. Construa umaGLC tal que: L(G) = {w|w ∈ {0, 1, 2}+ e todos os 0′s sejam consecutivos}
4. SejaG = ({S,B,C}, {a, b, c}, P, S), comP = {S → aS|bB,B → cB|cC,C →
cS|c}. Pede-se:
(a) determine L(G)
(b) construa G′, tal que L(G′) = L(G) ∪ {ε}
(c) verifique se as palavras abaixo pertencem a L(G):
• abccc
• accabcc
• bcccabcc
• abccbbc
7
4 Autômatos Finitos
São máquinas de estados finitos que reconhecem linguagens regulares. São compostas
de três componentes:
Fita: dividida em células e armazena a informação a ser processada
Unidade de Controle: registra o estado da máquina. A cabeça de leitura lê um sím-
bolo de cada vez da fita e movimenta-se somente para a direita.
Função de Transição: Baseada no símbolo lido e o estado corrente da máquina, de-
termina um novo estado.
Restrições:
• A fita é finita para os dois lados e a entrada ocupa toda a fita;
• Pode-se apenas realizar leituras na fita;
• Existe um número finito e pré-definido de estados;
• A cabeça de leitura começa na célula mais a esquerda da fita.
4.1 Autômatos Finitos Determinísticos
Exemplo:
Um autômato finito que reconhece palavras sobre o vocabulário {a, b} que contenham
aa ou bb como subpalavras. Toda informação necessária para o processamento da
entrada deve ser codificada através dos estados. Assim, começaremos com o estado
inicial q0, onde nenhum símbolo ainda foi lido. O estado q1 sinalizará que já foi lido
um a e caso outro seja lido, a palavra poderá terminar. O estado q2 tem o mesmo papel
que q1, porém para o símbolo b. E finalmente o estado q3 sinaliza o estado em que já
foram encontradas as subpalavras aa ou bb e neste ponto a palavra pode terminar ou
ainda ter qualquer sequência de a’s ou b’s. A figura 2 mostra o diagrama de transição
do autômato descrito acima.
Figura 2: Autômato finito determinístico que reconhece palavras contendo aa ou bb
como subpalavras.
8
Definição 4.1 (Autômato Finito Determinístico - AFD)Um autômato finito determi-
nístico é definido por:
A = (Q,Σ, δ, q0, F ), onde
• Q é um conjunto finito de estados;
• Σ é um alfabeto (símbolos de entrada);
• δ:Q× Σ→ Q é uma função parcial (função de transição);
• q0 ∈ Q é o estado inicial;
• F ⊆ Q é o conjunto de estados finais.
Exemplo: definição formal do autômato ilustrado na figura 2.
A = ({q0, q1, q2, q3}, {a, b}, δ, q0, {q3}), onde
δ(q0, a) = q1 δ(q0, b) = q2
δ(q1, a) = q3 δ(q1, b) = q2
δ(q2, a) = q1 δ(q2, b) = q3
δ(q3, a) = q3 δ(q3, b) = q3
Outra representação: através de matrizes de transições. O estado inicial é marcado
com→ e os estados finais são marcados com ∗.
Exemplo: a matriz de transições correspondente ao ADF da figura 2 é mostrada a
seguir:
δ a b
→ q0 q1 q2
q1 q3 q2
q2 q1 q3
∗q3 q3 q3
Exercícios 4.1
1. Construa o diagrama de transições de um AFD que reconhece a linguagem
{anb|n ≥ 1}.
2. Represente o AFD definido no exercício anterior formalmente e através da ma-
triz de transições.
9
4.2 Palavra aceita por um AFD
Um autômato finito determinístico aceita uma palavra w = a1a2 . . . an quando existe
um caminho no diagrama de transições, tal que:
• Começa no estado inicial;
• Termina em um estado final;
• Tem a sequência de rótulos a1a2 . . . an.
Exemplo: considere o autômato finito a seguir:
Este autômato aceita a palavra 01101 pois possui o caminho
q0
0→ q1 1→ q2 1→ q2 0→ q2 1→ q2
que satisfaz as restrições citadas acima.
Definição 4.2 Dado um AFD A = (Q,Σ, δ, q0, F ), a extensão da função de transição
para o domínio Q× Σ∗ é a função δˆ:Q× Σ∗ → Q definida por:
Base: δˆ(q, ε) = q
Indução: δˆ(q, wa) = δ(δˆ(q, w), a)
Exemplo: considerando o AFD anterior, vamos calcular δˆ(q0, 0110).
δˆ(q0, 0110) = δ(δˆ(q0, 011), 0) = δ(q2, 0) = q2
δˆ(q0, 011) = δ(δˆ(q0, 01), 1) = δ(q2, 1) = q2
δˆ(q0, 01) = δ(δˆ(q0, 0), 1) = δ(q1, 1) = q2
δˆ(q0, 0) = δ(δˆ(q0, ε), 0) = δ(q0, 0) = q1
δˆ(q0, ε) = q0
Portanto, δˆ(q0, 0110) = q2
Se δˆ(q, v) = p, então significa que o autômato chega no estado p quando reconhece a
palavra v a partir do estado q. Assim podemos dizer que a palavra v é aceita pelo AFD
se q e p são, respectivamente, o estado inicial e um estado final deste autômato.
Definição 4.3 (Linguagem aceita por umAFD)Dado um AFDA = (Q,Σ, δ, q0, F ),
a linguagem aceita por A é definida por:
L(A) = {w|w ∈ Σ∗ ∧ δˆ(q0, w) ∈ F}
10
Exercícios 4.2 Defina um AFD que reconheça datas válidas (não considerando anos
bissextos) no formato “mês/dia”, onde o mês e o dia devem ser representados por dois
dígitos.
11
4.3 Autômatos Finitos Não-Determinísticos
Um autômato finito é dito não-determinístico quando para um mesmo estado e um
mesmo símbolo há diferentes transições, isto é, o autômato pode assumir mais de um
estado simultaneamente.
Exemplo:
A figura 3 ilustra um autômato finito não-determinístico que reconhece palavras sobre
o vocabulário {0, 1} e terminam com a sentença 01.
Figura 3: Autômato finito não-determinístico que aceita palavras sobre o vocabulário
{0, 1}, terminadas em 01.
Definição 4.4 (Autômato Finito Não-Determinístico - AFN) Um autômato finito
não-determinístico é definido por:
N = (Q,Σ, δ, q0, F ), onde
• Q é um conjunto finito de estados;
• Σ é um alfabeto (símbolos de entrada);
• δ:Q× Σ→ P(Q) é a função de transição;
• q0 ∈ Q é o estado inicial;
• F ⊆ Q é o conjunto de estados finais.
Exemplo:
A definição formal do AFN definido na figura 3 é dada por:
N = ({q0, q1, q2}, {0, 1}, δ, q0, {q2}), onde
δ(q0, 0) = {q0, q1} δ(q0, 1) = {q0}
δ(q1, 0) = ∅ δ(q1, 1) = {q2}
δ(q2, 0) = ∅ δ(q2, 1) = ∅
E a matriz de transições:
δ 0 1
→ q0 {q0, q1} {q0}
q1 ∅ {q2}
∗q2 ∅ ∅
12
4.4 Palavra aceita por um AFN
Um autômato finito não-determinístico aceita uma palavra quando existe pelo menos
um caminho w = a1a2 . . . an quando existe pelo menos um caminho no diagrama de
transições, tal que:
• Começa no estado inicial;
• Termina em um estado final;
• Tem a sequência de rótulos a1a2 . . . an.
Exemplo: considere o AFN da figura 3. Para processar a palavra 00101 temos diversos
caminhos:
q0
0→ q1
q0
0→ q0 0→ q1 1→ q2
q0
0→ q0 0→ q0 1→ q0 0→ q0 1→ q0
Porém a única que que satisfaz as restrições citadas acima é a terceira.
Definição 4.5 Dado um AFNN = (Q,Σ, δ, q0, F ), a extensão da função de transição
para o domínio Q× Σ∗ é a função δˆ:Q× Σ∗ → P(Q) definida por:
Base: δˆ(q, ε) = {q}
Indução: δˆ(q, wa) =
⋃
p∈δˆ(q,w) δ(p, a)
Exemplo: considerando o AFN da figura 3, vamos calcular δˆ(q0, 0101).
δˆ(q0, 0101) =
⋃
p∈δˆ(q0,010) δ(p, 1) = δ(q0, 1) ∪ δ(q1, 1) = {q0, q2}
δˆ(q0, 010) =
⋃
p∈δˆ(q0,01) δ(p, 0) = δ(q0, 0) ∪ δ(q2, 0) = {q0, q1}
δˆ(q0, 01) =
⋃
p∈δˆ(q0,0) δ(p, 1) = δ(q0, 1) ∪ δ(q1, 1) = {q0, q2}
δˆ(q0, 0) =
⋃
p∈δˆ(q0,ε) δ(p, 0) = δ(q0, 0) = {q0, q1}
δˆ(q0, ε) = {q0}
Portanto, δˆ(q0, 0101) = {q0, q2}
Se δˆ(q, v) = {p1, . . . , pn}, então significa que o autômato chega aos estados p1, . . . , pn
quando reconhece a palavra v a partir do estado q. Assim podemos dizer que a palavra
v é aceita pelo AFN se q o estado inicial e se existe pelo menos um 1 ≤ i ≤ n, tal que
pi é um estado final deste autômato.
Definição 4.6 (Linguagem aceita por umAFN)Dado um AFNN = (Q,Σ, δ, q0, F ),
a linguagem aceita por N é definida por:
L(N) = {w|w ∈ Σ∗ ∧ δˆ(q0, w) ∩ F 6= ∅}
13
Exercícios 4.3
1. Defina um AFD paracada uma das seguintes linguagens:
(a) {w|w ∈ {a, b, c, d}∗ e w tem um número par de símbolos “b”}.
(b) {w|w ∈ {a, b, c, d}∗ e w contém a sequência “aab” }.
(c) {w|w ∈ {0, 1}∗ e w possui um número par de 0’s e um número ímpar de
1’s.
2. Considere os seguintes AFD com Σ = {0, 1}:
A = ({s0, s1},Σ, δA, s0, {s1}) e B = ({s0, s1, s2},Σ, δB , s0, {s1, s2})
com as funções de transições dadas por:
δA(s0, 0) = s0 δB(s0, 0) = s1
δA(s0, 1) = s1 δB(s0, 1) = s2
δA(s1, 0) = s0 δB(s1, 1) = s2
δA(s1, 1) = s1 δB(s2, 0) = s1
(a) Represente cada um dos autômatos por um diagrama de transições.
(b) Diga quais das seguintes palavras são aceitas pelos autômatos:
• ε
• 101
• 111
• 11001
• 01010
• 00011
(c) Determine δˆB(s0, 0101) mostrando a sequência de passos para encontrar
o resultado.
(d) Quais as linguagens definidas pelos autômatos (descreva informalmente)?
3. Defina AFNs que reconheçam as seguintes linguagens:
(a) conjunto de palavras sobre o alfabeto {a, b, c} tal que o sufixo seja “abc”
ou “bca”.
(b) conjunto de palavras sobre o alfabeto {0, 1, 2} tal que o digito final tenha
aparecido antes.
(c) conjunto de palavras sobre o alfabeto {x, y} tal que possuam “xx” ou “yy”
como subpalavra.
4. Considere o seguinte AFN com Σ = {a, b}:
X = ({A,B,C,D,E},Σ, δ, A, {A,D,E})
14
com a função de transições dada por:
δ(A, a) = {B,D} δ(A, b) = ∅
δ(B, a) = ∅ δ(B, b) = {C}
δ(C, a) = {B,D} δ(C, b) = ∅
δ(D, a) = ∅ δ(D, b) = {E}
δ(E, a) = ∅ δ(E, b) = {E}
(a) Represente o autômato por um diagrama de transições.
(b) Diga quais das seguintes palavras são aceitas por X:
• ε
• ababab
• abba
• abaab
• abbb
(c) Determine δˆ(A, abab) mostrando a sequência de passos para encontrar o
resultado.
(d) Qual a linguagem definida por X (descreva informalmente)?
15
4.5 Equivalência de AFNs e AFDs
Se uma linguagem L é aceita por um Autônomo Finito Não-determinístico
então existe um Autônomo Finito Determinístico que aceita L e vice-versa.
Construção dos Subconjuntos
Construção de todos os subconjuntos do espaço de estados de um AFN.
Exemplo:
(autômato finito não-determinístico) (autômato finito determinístico equivalente)
Para reduzir o tempo de construção, pode-se considerar apenas os estados alcançáveis
a partir do estado inicial. Assim, o AFD obtido a partir do AFN ilustrado acima, seria
como segue:
Definição 4.7 (Construção AFN → AFD) Seja N = (QN ,ΣN , δN , q0N , FN ) um
AFN. Definimos o AFD equivalente D = (QD,ΣD, δD, q0D, FD) da seguinte forma:
• QD = P(QN )
• ΣD = ΣN
• q0D = {q0N}
• FD = {S ∈ QD|S ∩ FN 6= ∅}
16
• Para cada S ∈ QD e a ∈ ΣD, tem-se:
δD(S, a) =
⋃
p∈S
δN (p, a)
Exercícios 4.4 Construa um AFD a partir do AFN a seguir, eliminando os estados
inalcançáveis:
(autômato finito não-determinístico)
Teorema 1 Se D = (QD,Σ, δD, q0D, FD) é um AFD obtido do AFN N = (QN , Σ,
δN , q0N , FN ) através da construção dos subconjuntos, então L(D) = L(N).
Prova: por indução em |v| que:
δˆD({q0}, v) = δˆN (q0, v)
Base: |v| = 0, v = ε
δˆD({q0}, ε) = {q0} pela def. de δˆ para AFDs
δˆN (q0, ε) = {q0} pela def. de δˆ para AFNs
Portanto, δˆD({q0}, ε) = δˆN (q0, ε)
Hipótese: |v| = n, v = w
δˆD({q0}, w) = δˆN (q0, w) = {p1, . . . , pk}
Passo: |v| = n+ 1, v = wa
(1) δˆD({q0}, wa) = δD(δˆD({q0}, w), a) pela def. de δˆ para AFDs
= δD({p1, . . . , pk}, a) pela hipótese
= δN (p1, a) ∪ . . . ∪ δN (pk, a) pela construção dos subconjuntos
(2) δˆN (q0, wa) =
⋃
p∈δˆN (q0,w) δN (p, a) pela def. de δˆ para AFNs
=
⋃
p∈{p1,...,pk} δN (p, a) pela hipótese
= δN (p1, a) ∪ . . . ∪ δN (pk, a)
Por (1) e (2) temos que δˆD({q0}, v) = δˆN (q0, v) = S
17
Além disso, temos que v é aceita por N sempre que S ∩ FN 6= ∅ e é aceita por
D sempre que S ∈ FD. Pela construção dos subconjuntos temos que:
S ∈ FN 6= ∅ → S ∈ FD
Com isso temos que v é aceita por ambos D e N se S possuir algum elemento
de FN , consequentemente L(D) = L(N).
√
Teorema 2 Uma linguagem L é aceita por um AFD se e somente se ela é aceita por
um AFN.
Prova:
(se) L ∈ L(AFN)→ L ∈ L(AFD) é verdadeiro pelo Teorema 1.
(somente se) L ∈ L(AFD)→ L ∈ L(AFN)
1. Converte-se um AFD em um AFN idêntico:
Dado um AFDD = (Q,Σ, δD, q0, F ) podemos obter um AFN equivalente
N = (Q,Σ, δN , q0, F ), onde δN é definido por
δD(q, a) = p→ δN (q, a) = {p}
2. Prova-se por indução em |v| que:
δˆD(qo, v) = p→ δˆN (q0, v) = {p}.
Esta prova é análoga a do Teorema 1. Com isso temos que L(D) = L(N).
√
18
4.6 Autômatos Finitos com Transições Vazias - AFNε
Não aumentam o poder de expressão dos autômatos finitos, apenas proporcionam con-
veniências de “programação”. São úteis para estabelecer a equivalência entre autôma-
tos finitos e expressões regulares.
Exemplo: AFNε que reconhece números com parte decimal composto da forma a se-
guir:
1. Sinal + ou −, opcional
2. w1 ∈ {0, 1, . . . , 9}+
3. “.” (ponto), opcional
4. w2 ∈ {0, 1, . . . , 9}∗
Definição 4.8 (Autômatos Finitos com Transições Vazias - AFNε) Um AFNε é uma
quíntupla
E = (Q,Σ, δ, q0, F ), onde
Q é o conjunto de estados
Σ é o alfabeto
δ:Q× (Σ ∪ {ε})→ P(Q) é a função de transição
q0 ∈ Q é o estado inicial
F ⊆ Q é o conjunto de estados finais
Definição 4.9 (Função fecho vazio de um estado ou conjunto de estados) A função
Fechoε:Q→ P(Q) é definida recursivamente por:
Base: q ∈ Fecho-ε(q)
Indução: se p ∈ Fecho-ε(q), então δ(p, ε) ⊆ Fecho-ε(q)
Fecho-ε({p1, . . . , pk}) = Fecho-ε(p1) ∪ . . . ∪ Fecho-ε(pk).
Exemplo: Considere o AFNε a seguir:
19
Fecho-ε(q1) = {q1, q2, q3, q4, q6}
Fecho-ε(q4) = {q4}
Fecho-ε(q5) = {q5, q7}
Definição 4.10 Dado um AFNε E = (Q,Σ, δ, q0, F ), a extensão da função de transi-
ção para o domínio Q× Σ∗ é a função δˆ:Q× Σ∗ → P(Q), definida por:
Base: δˆ(q, ε) = Fecho-ε(q)
Indução: δˆ(q, wa) = Fecho-ε(S), onde S =
⋃
p∈δˆ(q,w) δ(p, a)
Definição 4.11 (Linguagem aceita por umAFNε)Dado um AFNε E = (Q,Σ, δ, q0, F ),
a linguagem aceita por E é definida por:
L(E) = {w|w ∈ Σ∗ ∧ δˆ(q0, w) ∩ F 6= ∅}
Exercícios 4.5 Considere o AFNε a seguir:
1. Compute o Fecho-ε para cada estado.
2. Determine δˆ(p, abbc), mostrando a sequência de passos para encontrar o resul-
tado.
20
4.7 Equivalência entre AFNε e AFD
Se uma linguagem L é aceita por um Autônomo Finito com Transições Vazias
então existe um Autônomo Finito Determinístico que aceita L e vice-versa.
Construção AFNε→ AFD
Dado um AFNε E = (QE ,Σ, δE , q0E , FE). O AFD equivalente a E é definido por:
D = (QD,Σ, δD, q0D, FD), onde
QD = {S|S ∈ P(QE) ∧ S = Fecho-ε(S)}
q0D = Fecho-ε(q0E)
FD = {S|S ∩ FE 6= ∅ ∧ S ∈ QD}
Para todo S = {p1, . . . , pk} ∈ QD e todo a ∈ Σ:
δ(S, a) = Fecho-ε({r1, . . . , rn}), onde
{r1, . . . , rn} = δE(p1, a) ∪ . . . ∪ δE(pk, a)
Exemplo: Considere o AFNε:
O AFD equivalente é como segue:
(AFD equivalente com estados inalcançáveis) (AFD equivalente)
21
Exercícios 4.6
1. Converta o AFNε a seguir em um AFD:
(AFNε)
2. Considere o AFNε a seguir:
(a) Calcule o Fecho-ε para cada estado.
(b) Calcule δˆ(p, caab).
(c) Converta o AFNε para um AFD.
3. Defina AFNε’s para as linguagens a seguir. Tente usar transições ε para simpli-
ficar as definições.
(a) Conjunto de todas as palavras contendo zero ou mais 0’s seguidos por zero
ou mais 1’s seguidos por zero ou mais 2’s.
(b) Conjunto de todas as palavras contendo ab repetido uma ou mais vezes ou
contendo aba repetido uma ou mais vezes.
Teorema 3 Uma linguagem L é aceita por um AFNε se e somente se L é aceita por
um AFD.
Prova (esquema):
(se) L ∈ L(AFD)→ L ∈ L(AFNε)
1. Construir o AFNε E a partir do AFD D: o automato D é idêntico ao E,
alterando-se a função de transição da seguinte forma:
δD(q, a) = p⇒ δE(q, a) = {p}
22
e acrescenta-se para todo estado q
δE(q, ε) = ∅;
2. Provar que L(E) = L(D) por indução.
(somente se) L ∈ L(AFNε)→ L ∈L(AFD)
1. Construir o AFDD a partir do AFNε E através da construção apresentada
acima;
2. Provar que L(E) = L(D) por indução.
23
4.8 Equivalência entre AFNε e GR
Se uma linguagem L é gerada por uma Gramática Regular
então existe um Autônomo Finito com Transições Vazias que aceita L e vice-versa.
Construção GR→ AFNε
Considere a GR a seguir:
G = ({S,A,B}, {0, 1}, {S → A|ε,A→ 0B,B → 0B|1A|0}, S)
Observe que todas as regras da gramática possuem no máximo um terminal. Esta
gramática pode ser chamada de gramática linear a direita. Qualquer GR pode ser trans-
formada em uma gramática linear (unitária) à direita. Por exemplo: se uma gramática
regular possui a regra X → abcX , podemos substituir esta regra pelas regras a seguir,
mantendo no máximo um terminal por regra:
X → aX1
X1 → bX2
X2 → cX
Definição 4.12 Dada umaGR linear (unitária) à direitaG(N,T, P, S), podemos cons-
truir um AFNε equivalente da seguinte forma:
E = (Q,Σ, δ, qo, F ), onde
Q = N ∪ {X}, onde X 6∈ N
Σ = T
q0 = S
F = {X}
Para B ∈ N e a ∈ Σ:
δ(B, a) = {C|B → aC ∈ P} ∪ {X|B → a ∈ P}
δ(B, ε) = {C|B → C ∈ P} ∪ {X|B → ε ∈ P}
δ(X, a) = ∅
δ(X, ε) = ∅
AFNε equivalente a gramática G definida anteriormente:
24
Construção AFNε→ GR
Exemplo: Considere o AFNε a seguir:
A gramática regular equivalente é dada a seguir:
G = ({Q0, Q1, Q2, Q3}, {+,−, ·, 0, . . . , 9}, P,Q0), onde
P = {Q0 → Q1|+Q1| −Q1,
Q1 → 0Q1| . . . |9Q1|0Q2| . . . |9Q2,
Q2 → Q3| ·Q3,
Q3 → 0Q3| . . . |9Q3|ε}.
Definição 4.13 Dado um AFNε E = (Q,Σ, δ, qo, F ) podemos construir uma GR equi-
valente da seguinte forma:
G(Q,Σ, P, q0), onde
P é definido por:
− se C ∈ δ(B, a), então B → aC ∈ P
− se C ∈ F , então C → ε ∈ P
− se C ∈ δ(B, ε), então B → C ∈ P
Exercícios 4.7
1. Construir o AFNε equivalente à gramática a seguir:
G = ({S,A,B,C}, {a, b, c}, P, S), onde
P = {S → ε|A,
A→ aA|bB,
B → cB|cC,
C → cA|c}.
25
2. Construir a GR equivalente ao autômato a seguir:
Teorema 4 Uma linguagem L é reconhecida por um AFNε se e somente se L é gerada
por uma GR.
Prova (esquema):
(se) L ∈ L(GR)→ L ∈ L(AFNε)
1. Dada uma GR G = (N,T, P, S), constrói-se E = (N ∪ {X}, T, δ, S, F )
2. Provar que L(G) = L(E):
• Se v ∈ L(G) então E aceita x
– Sev = a1a2 . . . an ∈ L(G), então S ⇒+ v.
Como G é uma GR, a derivação S ⇒+ v é da forma:
S ⇒ a1A1 ⇒ a1a2A2 ⇒ . . .⇒ a1a2 . . . an−1An−1 ⇒ a1a2 . . . an
Logo,
S → a1A1,
A1 → a2A2,
...
An−1 → an
são produções de G.
Assim sendo, por definição de E:
A1 ∈ δ(S, a1),
A2 ∈ δ(A1, a2),
...
X ∈ δ(An−1, an)
Portanto, como v = a1a2 . . . an, X ∈ δˆ(S, v) e X ∈ F , conclui-
se que v ∈ L(E).
– Se v = ε ∈ L(G), então S ⇒+ ε e portanto S → ε ∈ P .
Neste caso, por definição, X ∈ δˆ(S, ε) e X ∈ F , conclui-se que
ε ∈ L(E).
26
• Se v ∈ L(E) então G gera v.
– Se v = a1a2 . . . an ∈ L(E), então existe uma sequência de esta-
dos
S,A1, A2, ..., An−1, X tal que
A1 ∈ δ(S, a1),
A2 ∈ δ(A1, a2),
...
X ∈ δ(An−1, an), onde S é o estado inicial e X é um estado
final.
Por definição, para que essas transições existam, G deverá pos-
suir as seguintes produções:
S → a1A1,
A1 → a2A2,
...
An−1 → an
e, se essas produções existem, então
S ⇒ a1A1 ⇒ a1a2A2 ⇒ . . .⇒ a1a2 . . . an−1An−1 ⇒ a1a2 . . . an
é uma derivação em G;
logo, como v = a1a2 . . . an e S ⇒+ v, conclui-se que L(G)
contém v.
– Se v = ε ∈ L(E).
Neste caso, existe a seguinte transição: X ∈ δ(S, ε)
Por definição, para que essa transição exista, G deverá possuir a
seguinte produção: S → ε. Assim, existe a derivação S ⇒+ ε.
Logo ε ∈ L(G).
(somente se) L ∈ L(AFNε)→ L ∈ L(GR)
1. Dado um AFNε E = (Q,Σ, δ, q0, F ), constrói-se G = (Q,Σ, P, q0);
2. Provar que L(E) = L(G) por indução.
Isto pode ser feito de maneira análoga a demonstração do se
27
4.9 Minimização de Autômatos Finitos
Um AFD A = (Q,Σ, δ, qo, F ) é mínimo se:
1. Não possui estados inacessíveis;
2. Não possui estados mortos;
3. Não possui estados equivalentes.
Estados Inacessíveis: Um estado q ∈ Q é inacessível (ou inalcançável) quando não
existe w tal que δˆ(q0, w) = q, onde w é uma palavra ou parte dela.
Estados mortos: Um estado q ∈ Q é morto se q 6∈ F e não existew, tal que δˆ(q, w)∩
F 6= ∅, ou seja, q é morto se ele não é final e a partir dele nenhum estado final pode ser
alcançado.
Estados Equivalentes: Um conjunto de estados {q1, . . . , qk} são equivalentes entre
si, se eles pertencem a uma mesma classe de equivalência.
Classes de Equivalência (CE): Um conjunto de estados {q1, . . . , qk} está em uma
mesma CE [q], se δ(q1, a) = p1, . . . , δ(qk, a) = pk, para cada a ∈ Σ, e p1, . . . , pk,
pertencem a uma mesma CE [p].
Definição 4.14 (Construção das Classes de Equivalência)
1. Divida Q em duas CE, uma contendo F e outra contendo Q− F ;
2. Divida as CE existentes, formando novas CE (de acordo com a definição de CE),
até que nenhuma nova CE seja formada.
Exemplo: Construa o conjunto de classes de equivalência do AFD a seguir:
28
[A,B,C,D,E, F,G,H]
fffff
fffff
fffff
fffff
fff
WWWWW
WWWWW
WWWWW
WWWWW
W
[B,C,E, F,H]
ppp
ppp
ppp
pp
OOO
OOO
OOO
OO
[A,D,G]
[B,F ] [C,E,H] [A,D,G]
tt
tt
tt
tt
t
HH
HH
HH
HH
H
[B,F ] [C,E,H]
ooo
ooo
ooo
oo
RRR
RRR
RRR
RRR
RRR
[A,G] [D]
[B,F ] [C,E] [H] [A,G] [D]
Construção de umAFDMínimo: Dado umAFD, sem estados inacessíveis ou mortos,
A = (Q,Σ, δ, q0, F ), pode-se obter um autômato mínimo equivalente como segue:
M = (Q′,Σ, δ′, q′0, F
′), onde
Q′ é o conjunto de CE de A;
q′0 é a CE que contém q0;
F ′ é o conjunto das CE que contenham pelo menos um elemento de F ;
δ′([p], a) = [q]⇔ δ(p1, a) = q1 é uma transição de A e p1 e q1 são elementos de [p] e
[q], respectivamente.
Exemplo: Autômato mínimo equivalente ao AFD definido a cima. OBS.: Os estados
D e H são eliminados pois são estados inacesssíveis.
M = (Q, {a, b}, δ, [A,G], {[A,G]}), onde
δ([B,F ], a) = [B,F ] δ([B,F ], b) = [C,E]
δ([C,E], a) = [C,E] δ([C,E], b) = [A,G]
δ([A,G], a) = [A,G] δ([A,G], b) = [B,F ]
29
Exercícios 4.8 Minimizar os autômatos a seguir:
30
5 Expressões Regulares
Uma maneira declarativa de descrever linguagens regulares, isto é, um esquema que
descreva as palavras contidas em um linguagem regular.
Exemplo: 01∗ + 10∗, Esta expressão descreve todas as palavras que iniciam por 0 e
têm uma sequência de zero ou mais 1’s e todas as palavras que iniciam por 1 e têm uma
sequência de zero ou mais 0’s.
Definição 5.1 (Expressão Regular - ER) Uma expressão regular sobre um alfabeto
Σ é indutivamente definida como se segue:
1. ∅ é uma ER que denota a linguagem vazia;
2. ε é uma ER que denota a linguagem contendo exclusivamente a palavra vazia,
ou seja {ε};
3. Qualquer símbolo x pertencente ao alfabeto Σ é uma ER e denota a linguagem
contendo a palavra unitária x, ou seja {x};
4. Se r e s são ERs e denotam, respectivamente, as linguagens R e S, então:
(a) (r + s) é uma ER e denota a linguagem R ∪ S;
(b) (rs) é uma ER e denota a linguagem {uv|u ∈ R ∧ v ∈ S};
(c) (r∗) é uma ER e denota a linguagem R∗.
Observações:
1. Os parênteses podem ser omitidos, respeitando-se as seguintes prioridades de
operações:
Prioridade Operação
1 Fecho
2 Concatenação
3 União
2. Uma linguagem gerada por um expressão regular r é representada por L(r).
Exemplos:
(a)∗ = a∗ = {ε, a, aa, aaa, . . .}
a+ = {a, aa, aaa, . . .}
(a+ b)∗ = {ε, a, b, aa, ab, ba, bb, aaa, . . .}
a+ b∗ = {ε, a, b, bb, bbb, . . .}
a(a+ b)∗ = {a, ab, aa, aaa, aab, aba, abb, aaaa, . . .}
(a(a+ b))∗ = {ε, aa, ab, aaaa, abaa, aaab, . . .}
31
Identificadores de uma linguagem de programação: l(l + d)∗
Inteiro com sinal: (++ -)d+
Inteiro com/sem sinal: (++ -+ ε)d+
Linguagem contendo somente a palavra aa: aa.
Linguagem contendo todas as palavras que iniciam por b, seguido de zeroou
mais a’s: ba∗.
Linguagem contendo todas as palavras sobre o alfabeto a, b: (a+ b)∗.
Linguagem contendo todas as palavras contendo aa como subpalavra:
(a+ b)∗aa(a+ b)∗.
Linguagem contendo todas as palavras contendo exatamente dois b’s:
a∗ba∗ba∗.
Linguagem contendo todas as palavras que terminam com aa ou bb:
(a+ b)∗(aa+ bb).
Linguagem contendo todas as palavras que não possuem dois a consecutivos:
(a+ ε)(b+ ba)∗ ou (b+ ab)∗(a+ ε).
5.1 Leis Algébricas para ER’s
• União:
– Comutatividade: r + s = s+ r
– Associatividade: (r + s) + t = r + (s+ t)
– Identidade: r + ∅ = ∅+ r = r
– Idenpotência: r + r = r
• Concatenação:
– Associatividade: (rs)t = r(st)
– Identidade: rε = εr = r
– Anulação: r∅ = ∅r = ∅
– Distributividade sobre união: r(s+ t) = rs+ rt e (s+ t)r = sr + tr
• Fecho:
– (r∗)∗ = r∗
– ∅∗ = ε
– ε∗ = ε
– r+ = rr∗ = r∗r
32
– r∗ = r+ + ε
Exercícios 5.1
1. Determine um ER que denote o conjunto das palavras sobre {a, b, c} nos quais
cada b é seguido por pelo menos um c.
2. Desenvolva expressões regulares que gerem as seguintes linguagens sobre Σ =
{a, b}:
(a) {w|w tem um nu´mero par de a′s}
(b) {w|w tem um nu´mero de a′s que e´ divisivel por 3}
(c) {w|w na˜o possui aba como subpalavra}
3. Descreva, em português, os conjuntos denotados pelas seguintes ER’s:
(a) (1 + 01 + 001)∗(ε+ 0 + 00)
(b) (00 + 11 + (01 + 10)(00 + 11)∗(01 + 10))∗
33
5.2 Equivalência de ERs e AFNεs
Se uma linguagem L é aceita por uma Expressão Regular
então existe um Autônomo Finito que aceita L e vice-versa.
Construção ER→ AFNε
Exemplo: construir um AF para a expressão regular (0 + 1)∗1(0 + 1)
(a)
(b)
(c)
Definição 5.2 (Construção ER → AFNε) Dada uma expressão regular R sobre o
alfabeto Σ, podemos definir um AFNε indutivamente como segue:
Base
• Se R = ∅ o autômato equivalente é
34
• Se R = ε o autômato equivalente é
• Se R = a, tal que a ∈ Σ o autômato equivalente é
Indução
• Se R = r + s o autômato equivalente é
• Se R = rs o autômato equivalente é
• Se R = r∗ o autômato equivalente é
Construção AF → ER
Constrói-se um Autômato Finito Genérico (AFG) a partir do AF. Um AFG é um autô-
mato finito que possui expressões regulares como rótulos para as transições, ao invés
de símbolos.
35
Um AFG deve possuir algumas características:
1. devem haver apenas setas partindo do estado inicial;
2. deve haver apenas um estado final e podem somente chegar setas neste estado;
3. não devem haver multiplos rótulos ou múltiplas setas com mesma origem e des-
tino.
Para atender a essas características, pode-se:
1. incluir um estado inicial com uma seta partindo dele e chegando no antigo estado
inicial. O rótulo dessa seta é ε;
2. incluir um estado final com setas partindo dos antigos estados finais e chegando
nele. O rótulo dessas setas é ε;
3. uma seta com rótulos múltiplos ou múltiplas setas com a mesma origem e destino
é substituída por uma seta com a união dos rótulos anteriores como rótulo.
Determinar a ER eliminando estados:
1. Se o número de estados k > 2 constrói-se um AFG equivalente com k − 1
estados, até k = 2:
(a) seleciona-se um estado (exceto o inicial e o final) para eliminar;
(b) reorganiza-se as setas e os rótulos para manter os todos os caminhos possí-
veis anteriormente. O esquema abaixo mostra como reorganizar os rótulos:
2. Se k = 2 e há uma única seta do estado inicial ao final, o rótulo é a expressão
regular equivalente ao AF.
Exemplo: determinar a ER equivalente ao AF a seguir:
36
(a) Autômato Finito Genérico
(b) Eliminado o estado A
(c) Eliminado o estado B
Teorema 5 Uma linguagem L é aceita por um ER se e somente se ela é aceita por um
AF.
Prova (esquema):
(se) L ∈ L(ER) → L ∈ L(AF ). Considera-se o AF A construído a partir da ER R
e prova-se por indução, no número de operadores da ER, que L(R) = L(A).
(somente se) L ∈ L(AF ) → L ∈ L(ER). Considera-se a ER R obtida a partir
do AF A e prova-se por indução, no comprimento dos caminhos do AF, que
L(R) = L(A).
Exercícios 5.2
1. Determine os AFs equivalentes as ERs a seguir:
(a) (0 + 1)01
37
(b) 00(0 + 1)∗
2. Determine a ERs equivalente aos AFs a seguir:
(a)
(b)
3. Aplique as construções conhecidas para obter a GR equivalente a expressão
regular (b + ε)(a + bb)∗. ATENÇÃO: a gramática obtida deve ser o mais sim-
plificada possível.
38

Outros materiais