Apostila LF

EXEMPLO 2.14. Para começar determinaremos uma expressão regular no al-
fabeto {0, 1, . . . , 9} que denote os inteiros positivos no sistema decimal. À pri-
meira vista pode parecer que a expressão seja simplesmente
(0 ∪ 1 ∪ · · · ∪ 9)∗.
O problema é que isto inclui palavras como 00000, que não correspondem a um
número formado de maneira correta. A solução é não permitir que as palavras
comecem com o símbolo 0, tomando
(1 ∪ · · · ∪ 9)(0 ∪ 1 ∪ · · · ∪ 9)∗.
EXEMPLO 2.15. Já a expressão que denota os inteiros não negativos é
0 ∪ (1 ∪ · · · ∪ 9)(0 ∪ 1 ∪ · · · ∪ 9)∗.
3. EXERCÍCIOS 25
EXEMPLO 2.16. Finalmente, suponhamos que uma certa linguagem de pro-
gramação tem por variáveis todas as palavras nos símbolos 0, 1, . . . , 9, A,B,C,
. . . , Z que não começam por um número inteiro. A expressão regular que denota
as variáveis nesta linguagem de programação é
(A ∪B ∪ · · · ∪ Z)(A ∪B ∪ · · · ∪ Z ∪ 0 ∪ 1 ∪ · · · ∪ 9)∗.
3. Exercícios
(1) Seja Σ = {0, 1}. Se L1 = {0} e L2 = {1}∗, determine:
a) L1 ∪ L2 e L1 ∩ L2;
b) L∗1 e L∗2;
c) (L1 ∪ L2)∗;
d) L∗1 ∩ L2;
e) L1;
f) L2 ∩ L∗1.
(2) Se L é uma linguagem em um alfabeto Σ então LR = {wR : w ∈ L}. Se
L = {0} · {1}∗ calcule LR.
(3) Seja L uma linguagem no alfabeto Σ. Considerando que
L∗ = {ε} ∪ L ∪ L.L ∪ L.L.L ∪ . . . e
L+ = L ∪ L.L ∪ L.L.L ∪ . . . ,
o que podemos concluir a respeito de L se L+ = L∗ \ {ε}?
(4) Sejam Σ1 e Σ2 dois alfabetos e seja φ : Σ1 → Σ∗2 uma aplicação. Se L é
uma linguagem no alfabeto Σ1, mostre que φ(L∗) = φ(L)∗.
(5) Descreva em português o conjunto denotado por cada uma das expressões
regulares abaixo:
a) 1∗0;
b) 1∗0(0)∗
c) 111 ∪ 001;
d) (1 ∪ 00)∗;
26 2. EXPRESSÕES REGULARES
e) (0(0)∗1)∗;
f) (0 ∪ 1)(0 ∪ 1)∗00;
(6) Expresse cada uma das seguintes linguagens no alfabeto {0, 1} usando
uma expressão regular:
a) o conjunto das palavras de um ou mais zeros seguidos de um 1;
b) o conjunto das palavras de dois ou mais símbolos seguidos por três ou
mais zeros;
c) o conjunto das palavras que contêm uma sequência de 1s, de modo
que o número de 1s na sequência é congruente a 2 módulo 3, seguido
de um número par de zeros.
(7) Se r e s são expressões regulares, vamos escrever r ≡ s se e somente se
L(r) = L(s). Supondo que r, s e t são expressões regulares, mostre que:
a) (r ∪ r) ≡ r;
b) ((r · s) ∪ (r · t)) ≡ (r · (s ∪ t));
c) ((s · r) ∪ (t · r)) ≡ ((s ∪ t) · r);
d) (r∗ · r∗) ≡ r∗;
e) (r · r∗) ≡ (r∗ · r);
f) r∗∗ ≡ r∗;
g) (ε ∪ (r · r∗)) ≡ r∗;
h) ((r · s)∗ · r) ≡ (r · (s · r)∗);
i) (r ∪ s)∗ ≡ (r∗ · s∗)∗ ≡ (r∗ ∪ s∗)∗.
(8) Usando as identidades do exercício anterior, prove que
((abb)∗(ba)∗(b ∪ aa)) ≡ (abb)∗((ε ∪ (b(ab)∗a))b ∪ (ba)∗(aa)).
Observe que alguns parênteses e o símbolo “·” foram omitidos para faci-
litar a leitura.
CAPíTULO 3
Relação entre AFD’s e Expressões Regulares
Conforme já vimos, uma linguagem regular é uma linguagem que é aceita por
algum AFD. No capítulo anterior, estudamos as expressões regulares, uma forma
uniforme e compacta de descrever algumas linguagens. Neste capítulo, vamos
mostrar que toda linguagem regular pode ser denotada por uma expressão regu-
lar (de forma que o nome “expressão regular” é realmente apropriado). Para isso,
vamos mostrar que, para todo AFD A, podemos construir uma expressão regular
r tal que L(A) = L(r) e que podemos fazer isto através de um método algorít-
mico. Na verdade, existe mais de um algoritmo capaz de calcular r, mas um que
é bastante simples e intuitivo é o algoritmo de substituição desenvolvido por John
Brzozowski.
1. Introdução
Desejamos obter um algoritmo que, dado um autômato finito M, determine a
linguagem L(M) que ele aceita. O algoritmo é recursivo, e para poder descrevê-lo
começamos por generalizar a noção de linguagem aceita por um autômato.
Seja M um autômato finito definido pelos ingredientes (Σ, Q, q1, F, δ). Para
cada q ∈ Q definimos Lq como sendo a linguagem
Lq = {w ∈ Σ
∗ : (q, w) ⊢∗ (f, ε) onde f ∈ F}.
Em outras palavras, Lq é formada pelas palavras que levam o autômato do estado
q a algum estado final. Quando os estados do autômato forem numerados como
q1, . . . , qn, escrevermos Li em vez de Lqi para simplificar a notação. Portanto, se
q1 é o estado inicial de M, então
Lq1 = L1 = L(M).
27
28 3. RELAÇÃO ENTRE AFD’S E EXPRESSÕES REGULARES
Sejam p e q estados de M, e digamos que δ(p, σ) = q. Esta transição estabe-
lece uma relação entre as linguagens Lp e Lq. De fato, temos que (p, σ) ⊢ (q, ε) ao
passo que, se w ∈ Lq, então (q, w) ⊢∗ (f, ε). Combinado estas duas computações
obtemos
(p, σw) ⊢ (q, w) ⊢∗ (f, ε).
Portanto, {σ}Lq ⊆ Lp. Mais uma vez, com a finalidade de não sobrecarregar a
notação, eliminaremos as chaves, escrevendo simplesmente σLq ⊆ Lp.
A não ser que o alfabeto Σ tenha apenas um símbolo, não há a menor chance
de que σLq ⊆ Lp seja uma igualdade. Isto porque teremos uma inclusão como
esta para cada σ ∈ Σ. Portanto, se Σ = {σ1, . . . , σn} e se δ(p, σi) = qi, então
n⋃
i=1
σiLqi ⊆ Lp.
Desta vez, porém, a inclusão é, de fato, uma igualdade, desde que p não seja
um estado final do autômato! Para ver isto suponhamos que u ∈ Lp. Podemos
isolar o primeiro símbolo de u, escrevendo u = σiw, para algum σi ∈ Σ. Mas,
pela definição de Lp,
(p, u) = (p, σiw) ⊢
∗ (f, ε),
para algum f ∈ F . Por outro lado, como δ(p, σi) = qi, temos que (p, σi) ⊢ (qi, ε).
Combinando estas duas computações, temos que
(p, u) = (p, σiw) ⊢ (qi, w) ⊢
∗ (f, ε),
de onde segue que w ∈ Lqi .
Precisamos ainda analisar o que acontece quando p é um estado final do autô-
mato. Considerando em detalhe o argumento do parágrafo acima, vemos que as-
sumimos implicitamente que u 6= ε, já que estamos explicitando o seu primeiro
símbolo. Entretanto, se p for um estado final, teremos, além disso, que ε ∈ Lp.
1. INTRODUÇÃO 29
Resumindo, provamos que, se Σ = {σ1, . . . , σn}, e se δ(p, σi) = qi, então
Lp =


⋃n
i=1 σiLqi se p /∈ F⋃n
i=1 σiLqi ∪ {ε} se p ∈ F
O algoritmo que desejamos segue diretamente desta equação, como mostra o
seguinte exemplo.
EXEMPLO 3.1. Considere o autômato finito determinístico M com alfabeto
é {0, 1} e cujo grafo é
I // WVUTPQRSq1 0 //
1
��
WVUTPQRSq2 1 //
0
~~⑥⑥
⑥⑥
⑥⑥
WVUTPQRSONMLHIJKq3
0,1vv♥♥♥
♥♥♥
♥♥♥
♥♥♥
♥
WVUTPQRSq4
0,1
\\
Deste grafo extraímos as seguintes equações
L1 = 0L2 ∪ 1L4
L2 = 1L3 ∪ 0L4
L3 = 0L4 ∪ 1L4 ∪ {ε} (já que q3 é estado final)
L4 = 0L4 ∪ 1L4.
Observe que q4 é um estado morto, de modo que nada escapa de q4. Em
particular, nenhuma palavra leva o autômato de q4 a um estado final. Portanto,
L4 = ∅. Isto simplifica drasticamente as equações anteriores, que passam a ser
L1 = 0L2
L2 = 1L3
L3 = {ε}
L4 = ∅.
30 3. RELAÇÃO ENTRE AFD’S E EXPRESSÕES REGULARES
Podemos agora resolver este sistema de equações por mera substituição. Assim,
substituindo a terceira equação na segunda, obtemos
L2 = 1L3 = 1{ε} = {1}.
Finalmente, substituindo esta última equação na primeira, obtemos
L1 = 0L2 = 0{1} = {01}.
Como L1 = L(M), obtivemos uma descrição da linguagem aceita por M.
Como seria de esperar, as coisas nem sempre são tão diretas. Afinal, o autô-
mato deste exemplo tinha um comportamento muito simples. Vejamos o que acon-
tece em um exemplo menos elementar.
EXEMPLO 3.2. Seja N o autômato finito determinístico de alfabeto {0, 1} e
grafo
I // WVUTPQRSq1
0,1
,, WVUTPQRSONMLHIJKq2
0,1
ll
As equações correspondentes a L1 e L2 são:
L1 = 0L2 ∪ 1L2
L2 = 0L1 ∪ 1L1 ∪ {ε} (já que q2 é estado final)
Continuando a denotar {0} e {1} por 0 e 1, podemos re-escrever estas equações
como
L1 = (0 ∪ 1)L2
L2 = (0 ∪ 1)L1 ∪ {ε}.
À primeira vista, tudo o que temos que fazer para resolver este sistema é substituir
a segunda equação na primeira. Contudo, ao fazer isto obtemos