Apostila LF

como fizemos no exemplo anterior, esta característica da função se traduz no fato
de que a tabela é sempre completamente preenchida e cada campo da tabela possui
exatamente um estado. Já ao representarmos o AFD como um grafo, esta carac-
terística da função se traduz no fato de que cada vértice possui exatamente uma
aresta rotulada por cada símbolo do alfabeto saindo dele.
A grosso modo, um AFD é um dispositivo que processa uma palavra que re-
cebe como entrada (lembrando que, por nossa definição no capítulo anterior, pa-
lavras são sempre finitas) e fornece como saída uma resposta do tipo Sim/Não. O
AFD A = (Σ, Q, q0, F, δ) inicia seu processamento no estado q0 e recebe como
entrada uma palavraw ∈ Σ∗. Ele lê um símbolo dew de cada vez, começando pelo
seu primeiro símbolo mais à esquerda. Se o autômato se encontra em um estado q
e lê o símbolo σ, então, após a leitura, ele irá para o estado q′ = δ(q, σ).
A partir destas transições de estado, podemos definir a noção de uma compu-
tação do autômato com uma palavra w.
DEFINIÇÃO 1.4. Uma configuração do AFD A é um par formado por um
estado deA e uma palavra deΣ∗ (um elemento deQ×Σ∗). O primeiro componente
de uma configuração representa o estado atual do autômato, enquanto o segundo
componente representa o trecho da palavra de entrada que ainda não foi lida pelo
autômato.
DEFINIÇÃO 1.5. A relação de configuração seguinte (notação ⊢) é definida
como (q, w) ⊢ (q′, w′) se w = σw′ e δ(q, σ) = q′.
DEFINIÇÃO 1.6. Se C0, . . . , Cn são configurações de A e se C0 ⊢ . . . ⊢ Cn,
então temos uma computação em A, notação C0 ⊢∗ Cn (em particular, assumimos
que C0 ⊢∗ C0).
14 1. LINGUAGENS REGULARES E AUTÔMATOS FINITOS DETERMINÍSTICOS
DEFINIÇÃO 1.7. Dizemos que uma palavra w ∈ Σ∗ é aceita ou reconhecida
pelo AFD A se (q0, w) ⊢∗ (f, ε) e f ∈ F , isto é, se após a leitura de todos os
símbolos da palavra w, o autômato termina em algum de seus estados finais. Caso
contrário, dizemos que a palavra é rejeitada ou não aceita ou não reconhecida pelo
AFD A.
EXEMPLO 1.8. Consideramos o autômato descrito no exemplo anterior. Va-
mos descrever qual é a sua computação ao receber como entrada a palavra w1 =
10011.
(q1, 10011) ⊢ (q1, 0011) ⊢ (q2, 011) ⊢ (q1, 11) ⊢ (q1, 1) ⊢ (q1, ε)
Graficamente:
WVUTPQRSq1 1 // WVUTPQRSq1 0 // WVUTPQRSq2 0 // WVUTPQRSq1 1 // WVUTPQRSq1 1 // WVUTPQRSq1
Como o autômato termina esta computação no estado q1, que não é um dos seus
estados finais, a palavra w1 não é aceita pelo autômato.
EXEMPLO 1.9. Consideramos novamente o autômato descrito no exemplo
anterior e agora vamos descrever qual é a sua computação ao receber como entrada
a palavra w2 = 01101.
(q1, 01101) ⊢ (q2, 1101) ⊢ (q3, 101) ⊢ (q1, 01) ⊢ (q2, 1) ⊢ (q3, ε)
Graficamente:
WVUTPQRSq1 0 // WVUTPQRSq2 1 // WVUTPQRSONMLHIJKq3 1 // WVUTPQRSq1 0 // WVUTPQRSq2 1 // WVUTPQRSONMLHIJKq3
Como o autômato termina esta computação no estado q3, que é um dos seus estados
finais (o único estado final neste caso), a palavra w2 é aceita pelo autômato.
DEFINIÇÃO 1.10. Definimos a linguagem aceita por um AFD A com alfabeto
Σ, denotada por L(A), como sendo o conjunto de todas as palavras w ∈ Σ∗ que
são aceitas por A. Observe que temos L(A) ⊆ Σ∗.
2. EXERCÍCIOS 15
EXEMPLO 1.11. Consideramos novamente o autômato descrito no exemplo
anterior e agora vamos descrever qual é a sua computação ao receber como entrada
a palavra w3 = 001100.
(q1, 001100) ⊢ (q2, 01100) ⊢ (q1, 1100) ⊢ (q1, 100) ⊢ (q1, 00) ⊢ (q2, 0) ⊢ (q1, ε)
Graficamente:
WVUTPQRSq1 0 // WVUTPQRSq2 0 // WVUTPQRSq1 1 // WVUTPQRSq1 1 // WVUTPQRSq1 0 // WVUTPQRSq2 0 // WVUTPQRSq1
Como o autômato termina esta computação no estado q1, que não é um dos seus
estados finais, a palavra w3 não é aceita pelo autômato. Isto significa que w3 /∈
L(A).
EXEMPLO 1.12. Consideramos novamente o autômato descrito no exemplo
anterior e agora vamos descrever qual é a sua computação ao receber como entrada
a palavra w4 = 001101.
(q1, 001101) ⊢ (q2, 01101) ⊢ (q1, 1101) ⊢ (q1, 101) ⊢ (q1, 01) ⊢ (q2, 1) ⊢ (q3, ε)
Graficamente:
WVUTPQRSq1 0 // WVUTPQRSq2 0 // WVUTPQRSq1 1 // WVUTPQRSq1 1 // WVUTPQRSq1 0 // WVUTPQRSq2 1 // WVUTPQRSONMLHIJKq3
Como o autômato termina esta computação no estado q3, que é um dos seus estados
finais (o único estado final neste caso), a palavra w4 é aceita pelo autômato. Isto
significa que w4 ∈ L(A).
DEFINIÇÃO 1.13. Seja L uma linguagem. Dizemos que L é uma linguagem
regular se existe um AFD A tal que L = L(A), isto é, se é possível construir
um AFD tal que as palavras aceitas por ele sejam exatamente as palavras que
pertencem à linguagem L.
2. Exercícios
(1) Seja A um autômato finito determinístico. Quando é que ε ∈ L(A)?
16 1. LINGUAGENS REGULARES E AUTÔMATOS FINITOS DETERMINÍSTICOS
(2) Desenhe o grafo de estados de cada um dos seguintes autômatos finitos.
Em cada caso o estado inicial é q1 e o alfabeto é {a, b, c}.
a) F1 = {q5} e a função de transição é dada por:
δ1 a b c
q1 q2 q3 q4
q2 q2 q4 q5
q3 q4 q3 q5
q4 q4 q4 q5
q5 q4 q4 q5
b) F2 = {q4} e δ2 = δ1.
c) F3 = {q2} e a função de transição é dada por:
δ3 a b c
q1 q2 q2 q1
q2 q3 q2 q1
q3 q1 q3 q2
(3) Considere o autômato finito determinístico no alfabeto {a, b}, com esta-
dos {q0, q1}, estado inicial q0, estados finais F = {q1} e cuja função de
transição é dada por:
δ a b
q0 q0 q1
q1 q1 q0
a) Esboce o diagrama de estados deste autômato.
b) Descreva a computação deste autômato que tem início na configuração
(q0, aabba). Esta palavra é aceita pelo autômato?
c) Descreva a computação deste autômato que tem início na configuração
(q0, aabbab). Esta palavra é aceita pelo autômato?
d) Descreva em português a linguagem aceita pelo autômato definido
acima?
2. EXERCÍCIOS 17
(4) Seja Σ um alfabeto com n > 0 símbolos. Dado o valor de n e a quanti-
dade m > 0 de estados, quantos autômatos finitos determinísticos exis-
tem satisfazendo estes valores? (A resposta será em função de m e n.)
Sugestão: Não esqueça de considerar todas as possibilidades para o con-
junto de estados finais.
(5) Invente autômatos finitos determinísticos que aceitem as seguintes lin-
guagens sobre o alfabeto {0, 1}:
a) o conjunto das palavras que acabam em 00;
b) o conjunto das palavras com três 0s consecutivos;
c) o conjunto das palavras em que cada 0 está entre dois 1s;
d) o conjunto das palavras cujos quatro símbolos finais são 1101;
e) o conjunto dos palíndromos de comprimento igual a 6.
(6) Dê exemplo de uma linguagem que é aceita por um autômato finito deter-
minístico com mais de um estado final, mas que não é aceita por nenhum
autômato finito determinístico com apenas um estado final. Justifique
cuidadosamente sua resposta.
CAPíTULO 2
Expressões Regulares
Neste capítulo, apresentamos uma maneira compacta e uniforme de descrever
as linguagens regulares, isto é, as linguagens que são aceitas por autômatos finitos
determinísticos. Esta notação compacta é dada pelas expressões regulares.
1. Breve Motivação
Vamos observar novamente o exemplo do AFD A mostrado no capítulo ante-
rior. Reproduzimos novamente abaixo o seu grafo.
EXEMPLO 2.1.
I // WVUTPQRSq1
0
,,
1
BB
WVUTPQRSq2
0
ll
1~~⑥⑥
⑥⑥
⑥⑥
WVUTPQRSONMLHIJKq31
``❆❆❆❆❆❆
0
\\
Olhando para o grafo deste AFD, podemos tentar determinar as palavras que
pertencem a L(A). Serão palavras que descrevam um caminho de q1 até q3 no
grafo. Não é complicado descrever algumas possíveis palavras que satisfaçam essa
propriedade. O grande problema é que, para descrever L(A), precisamos ser ca-
pazes de descrever todas estas palavras. Mostramos abaixo a descrição, em portu-
guês, de algumas palavras que pertencem a L(A).
(1) A palavra começa com um número ímpar de 0’s, seguido de um único 1,
terminando com uma quantidade arbitrária