Linguagens Formais e Autômatos-133

Prévia do material em texto

4 Linguagens Livres de Contexto 265
3. F3 = F1 × F2;
4. δ3 definida como:
a) δ3((qi , qm), σ,X ) = {((qj , qn), γ)},
para δ1(qi , σ) = qj e δ2(qm , σ,X ) = {(qn , γ)};
b) δ3((qi , qm), ǫ,X ) = {((qi , qn), γ)},
para δ2(qm , ǫ,X ) = {(qn , γ)}.
É possível demonstrar (ver [46]), por indução sobre o tamanho das cadeias analisa-
das pelos autômatos, que ((q01, q02),w ,Z0) ⊢∗ ((qr , qs), ǫ, ǫ), (qr , qs) ∈ F3, se e somente
se (q01,w) ⊢∗ (qs , ǫ), qs ∈ F1 e (q02,w ,Z0) ⊢∗ (qr , ǫ, ǫ), qr ∈ F2.
Em outras palavras, M3 aceita w se e apenas se M1 e M2 também aceitam w . Se
M1 e/ou M2 rejeitam w , então M3 também rejeita w . Logo, L3 corresponde à intersecção
das linguagens L1 e L2, e a existência de M3 prova que L3 é uma linguagem livre de
contexto.
Este teorema mostra como construir um autômato de pilha M3 que simula, de
maneira simultânea, as configurações que podem ser assumidas por um outro autômato
de pilha M2 e um autômato finito determinístico M1 no reconhecimento de uma mesma
cadeia de entrada.
Assim, os estados de M3 correspondem ao produto cartesiano Q1 × Q2. Se M3 se
encontrar no estado (qi , qm), isso significa que, naquela situação, M1 encontrar-se-á no
estado qi e M2 no estado qm , se estivessem operando separadamente no reconhecimento
da mesma cadeia de entrada.
Se a entrada σ for aceita simultaneamente no estado qi de M1 e no estado qm de
M2, então uma nova transição é acrescentada em M3 com o símbolo σ partindo do estado
(qi , qm) e com destino no estado (δ1(qi), δ2(qm)).
Transições sem consumo de símbolo na cadeia de entrada de M2 — da forma
δ2(qi , ǫ,X ) = {(qj , γ)} — podem ser simuladas sem dificuldade em M3, bastando para
isso “preservar” o estado corrente de M1 em M3, uma vez que M1 é, por definição, deter-
minístico, isento de transições em vazio.
Pelo fato de M1 ser um autômato finito, que não necessita de pilha para operar, esta
é manipulada por M3 de forma a reproduzir a manipulação executada de forma isolada
por M2.
A cadeia de entrada será aceita se M3 atingir um estado final (composto por estados
finais de M1 e de M2) com a cadeia de entrada esgotada e com a pilha vazia. Nesta
configuração ocorre a aceitação simultânea da cadeia de entrada por M1 e M2. �
Exemplo 4.44 Sejam L1 = (ab∗ | ba∗) e L2 = (anbn+1 | bnan+1), respectivamente reconhecidas
pelo autômato finito M1 e pelo autômato de pilha M2 mostrados nas Figuras 4.28 e 4.29.
266 Linguagens Formais - Teoria, Modelagem e Implementação
q01
q11
q12
b
a
a
b
Figura 4.28: Autômato finito que reconhece L1 = (ab∗ |
ba∗)
q02
q21
q23
(a,Z0)/AZ0
(b,Z0)/BZ0
(a,A)/AA
(b,B)/BB
q22
q24
(b,A)/ǫ
(a,B)/ǫ
(b,Z0)/ǫ
(b,A)/ǫ
(a,Z0)/ǫ
(a,B)/ǫ
(ǫ,Z0)/Z0
(ǫ,Z0)/Z0
Figura 4.29: Autômato de pilha que reconhece L2 =
(anbn+1 | bnan+1)
A linguagem L3 = L1 ∩ L2 é reconhecida pelo autômato de pilha M3, construído conforme o
Algoritmo 4.14, utilizado na demonstração do Teorema 4.22:
Q3 = {(q01, q02), (q01, q21), (q01, q22), (q01, q23), (q01, q24),
(q11, q02), (q11, q21), (q11, q22), (q11, q23), (q11, q24),
(q12, q02), (q12, q21), (q12, q22), (q12, q23), (q12, q24)}
F3 = {(q11, q22), (q11, q24), (q12, q22), (q12, q24)}
δ3 = {((q01, q02), ǫ,Z0)→ ((q01, q21),Z0),
((q01, q02), ǫ,Z0)→ ((q01, q23),Z0),
((q01, q21), a,Z0)→ ((q12, q21),AZ0),
((q01, q21), a,A)→ ((q12, q21),AA),
((q01, q21), b,A)→ ((q11, q22), ǫ),
((q01, q22), b,Z0)→ ((q11, q22), ǫ),