A maior rede de estudos do Brasil

Grátis
271 pág.
Apostila LF

Pré-visualização | Página 7 de 49

= 0
∗1L4 ∪ 0
∗,
e continuamos com L4 dos dois lados da equação. Mas, ao invés de nos deixar
intimidar, aplicaremos o Lema de Arden a esta última equação, o que nos dá
(3.1) L4 = (0∗1)∗0∗.
Note que se isto estiver correto (e está!) então devemos ter que os conjuntos
(0∗1)∗0∗ e (0 ∪ 1)∗ são iguais–quer dizer, têm os mesmos elementos. Portanto,
deve ser possível mostrar que toda palavra no alfabeto {0, 1} pertence ao conjunto
(0∗1)∗0∗. Fica por sua conta se convencer disto. Finalmente, se adotarmos esta
última maneira de expressar L4, a descrição da linguagem aceita pelo autômato
que resulta do algoritmo de substituição é
010∗(011(0∗1)∗0∗).
Em particular, o algoritmo de substituição pode retornar linguagens diferentes, to-
das corretas, dependendo da maneira como for aplicado.
4. Análise Formal do Algoritmo de Substituição
Nesta seção damos uma descrição detalhada do algoritmo de substituição; isto
é, uma descrição cuidadosa o suficiente para servir, tanto para programar o algo-
ritmo, quanto para provar que funciona como esperado. Na verdade, encerramos
a seção justamente com uma demonstração de que o algoritmo está correto. Con-
tudo, se você não pretende programar o algoritmo, nem sente necessidade de uma
demonstração formal, talvez seja melhor pular esta seção.
38 3. RELAÇÃO ENTRE AFD’S E EXPRESSÕES REGULARES
Começamos com algumas definições um tanto técnicas. Para t = 0, . . . ,m
seja Σt o alfabeto definido por
Σt =


Σ se t = 0
Σ ∪ {α1, . . . , αt} se t ≥ 1.
Seja agora Θt o conjunto formado pelas expressões regulares em Σt da forma
⋃
i≤t
ηi · αi,
onde ηi 6= ε é uma expressão regular em Σ0 = Σ. Note que Θ0 é o conjunto das
expressões regulares em Σ.
Dado θ ∈ Θt, seja L(θ) a linguagem obtida de acordo com as seguintes regras:
(1) L(ε) = {ε};
(2) L(∅) = ∅;
(3) L(αi) = Li;
com Li como definido na seção 1, e se α e β são expressões regulares em Σt então
(4) L(α · β) = L(α) · L(β);
(5) L(α ∪ β) = L(α) ∪ L(β);
(6) L(α∗) = L(α)∗.
Estamos, agora, prontos para dar uma descrição minuciosa do funcionamento
do algoritmo.
Algoritmo de Substituição
Entrada: um autômato finito determinístico A cujos ingredientes são (Σ, Q, q0,
F, δ), onde Q = {q1, . . . , qn} e q0 = q1.
Saída: uma expressão regular r tal que L(r) = L(A).
Etapa 1: Para cada estado qi escreva uma expressão regular em Σm da forma
Ei =
⋃
{(σj · αj(i)) : δ(qi, σj) = qj(i)}
4. ANÁLISE FORMAL DO ALGORITMO DE SUBSTITUIÇÃO 39
se qm não é estado final, ou
Ei =
⋃
{(σj · αj(i)) : δ(qi, σj) = qj(i)} ∪ {ε}
se qm é estado final; e inicialize k = m.
Etapa 2: Se Ek já está escrito como uma expressão regular em Θk−1, vá para
(3), senão Ek é da forma
Ek = η · αk ∪B
onde B ∈ Θk−1. Neste caso escreva Ek = η∗ ·B e vá para para a Etapa 3. Observe
que pode acontecer que B = ∅; se isto ocorrer então Ek = ∅.
Etapa 3: Subtraia 1 de k. Se k = 0, então L(A) é denotada pela expressão re-
gular E1 no alfabeto Σ0 e podemos parar; senão, substitua αk por Ek na expressão
regular Ei para i 6= k e volte à Etapa 2.
Resta-nos apenas dar uma demonstração de que este algoritmo funciona. Fa-
remos isso usando indução finita.
DEMONSTRAÇÃO. Digamos que, para um certo inteiro 0 ≤ k ≤ m estamos
para executar o (m − k)-ésimo laço deste algoritmo. Queremos mostrar que, ao
final deste laço
(1) Ei ∈ Θk−1 e
(2) L(Ei) = Li,
para i = 1, . . . ,m. Para fazer isto, podemos supor que, chegados a este laço,
temos Ei ∈ Θk e L(Ei) = Li para i = 1, . . . ,m. Observe que estas duas últimas
afirmações são claramente verdadeiras quando k = m.
Começamos considerando a execução da Etapa 2 no (m − k)-ésimo laço. Se
já temos que Ek ∈ Θk−1 então nada há a fazer nesta etapa. Por outro lado, se
Ek /∈ Θk−1, então como Ek ∈ Θk podemos escrever
(4.1) Ek = ηk · αk ∪B,
40 3. RELAÇÃO ENTRE AFD’S E EXPRESSÕES REGULARES
onde B ∈ Θk−1. Seja F = η∗k ·B. Temos de (4.1) e (2) que
Ak = L(Ek) = L(ηk) ·Ak ∪ L(B).
Logo, pelo lema de Arden,
Ak = L(ηk)
∗ · L(B),
mas isto é igual a L(F ). Como o algoritmo manda fazer Ek = F , obtemos, ao
final desta etapa, que Ek ∈ Θk−1 e L(Ek) = Ak.
Finalmente, na etapa 3, basta substituir αk por F na expressão regular de Ej
sempre que j 6= k. Note que segue imediatamente disto que Ej ∈ Θk−1 e que
L(Ej) = Aj .
5. Último Exemplo
Nesta seção, retornamos ao exemplo da seção inicial do capítulo anterior e
mostramos como obter, utilizando o algoritmo de substituição, uma notação com-
pacta na forma de expressão regular para a linguagem aceita por aquele autômato.
EXEMPLO 3.5. Reproduzimos novamente abaixo o grafo daquele autômato.
I // WVUTPQRSq1
0
,,
1
BB
WVUTPQRSq2
0
ll
1~~⑥⑥
⑥⑥
⑥⑥
WVUTPQRSONMLHIJKq31
``❆❆❆❆❆❆
0
\\
As equações para este autômato são as seguintes:
L1 = 0.L2 ∪ 1.L1
L2 = 0.L1 ∪ 1.L3
L3 = 0.L3 ∪ 1.L1 ∪ ε
6. EXERCÍCIOS 41
Aplicando o Lema de Arden a L3, com A = 0 e B = 1.L1 ∪ ε, obtemos
L3 = 0
∗.(1.L1 ∪ ε) = 0
∗1L1 ∪ 0
∗.
Substituindo L3 nas equações de L1 e L2, obtemos as seguintes equações:
L1 = 0L2 ∪ 1L1
L2 = 0L1 ∪ 1(0
∗1L1 ∪ 0
∗) = (0 ∪ 10∗1)L1 ∪ 10
∗
Substituindo L2 na equação de L1, obtemos
L1 = 0((0 ∪ 10
∗1)L1 ∪ 10
∗) ∪ 1L1 = (0(0 ∪ 10
∗1) ∪ 1)L1 ∪ 010
∗.
Aplicando o Lema de Arden a L1, com A = 0(0∪ 10∗1)∪ 1 e B = 010∗, obtemos
L1 = (0(0 ∪ 10
∗1) ∪ 1)∗010∗.
Esta é a expressão regular que denota a linguagem aceita pelo autômato.
6. Exercícios
(1) Determine a linguagem aceita por cada um dos seguintes autômatos fini-
tos. 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:
42 3. RELAÇÃO ENTRE AFD’S E EXPRESSÕES REGULARES
δ3 a b c
q1 q2 q2 q1
q2 q3 q2 q1
q3 q1 q3 q2
(2) Para cada um dos autômatos finitos determinísticos, no alfabeto {0, 1},
dados abaixo:
• esboce o diagrama de estados;
• encontre os sorvedouros e os estados mortos;
• determine a expressão regular da linguagem aceita pelo autômato
usando o algoritmo de substituição.
a) Os estado são {q1, . . . , q4}, o estado inicial é q1, o conjunto de estados
finais é {q2} e a função de transição é dada por:
δ 0 1
q1 q2 q4
q2 q3 q1
q3 q4 q4
q4 q4 q4
b) Os estado são {q1, . . . , q5}, o estado inicial é q1, o conjunto de estados
finais é {q3, q4} e a função de transição é dada por:
δ 0 1
q1 q2 q4
q2 q2 q3
q3 q5 q5
q4 q5 q5
q5 q5 q5
c) Os estado são {q1, . . . , q4}, o estado inicial é q1, o conjunto de estados
finais é {q1} e a função de transição é dada por:
6. EXERCÍCIOS 43
δ 0 1
q1 q2 q4
q2 q3 q1
q3 q4 q2
q4 q4 q4
d) Os estado são {q1, q2, q3}, o estado inicial é q1, o conjunto de estados
finais é {q1} e a função de transição é dada por:
δ 0 1
q1 q1 q2
q2 q3 q2
q3 q1 q2
e) Os estado são {q1, . . . , q6}, o estado inicial é q1, o conjunto de estados
finais é {q4} e a função de transição é dada por:
δ 0 1
q1 q5 q2
q2 q5 q3
q3 q4 q3
q4 q4 q4
q5 q6 q2
q6 q6 q4
CAPíTULO 4
Autômatos Finitos Não-Determinísticos
Neste capítulo, apresentamos e estudamos uma generalização simples dos autô-
matos finitos determinísticos. Retiramos da função de transição do autômato a
propriedade do determinismo, obtendo os autômatos finitos não-determinísticos.
1. Autômatos Finitos Não-Determinísticos (AFND’s)
DEFINIÇÃO 4.1. Um autômato finito não-determinístico (abreviado como
AFND) A é uma 5-upla A = (Σ, Q, q0, F,∆), onde:
• Σ, Q, q0 e F são definidos da mesma forma que em um AFD e
• ∆ é a função de transição não-determinística. Esta função tem o formato
∆ : Q× (Σ ∪ {ε})→ P(Q),
isto é, para

Crie agora seu perfil grátis para visualizar sem restrições.