Exercício 11. Seja L uma linguagem livre de contexto e R uma linguagem regular. Descreva a construção de um PDA para mostrar como reconhecer a linguagem L \cap R e prove que sua construção está correta.

Passo 1

O enunciado pede para mostrar que, se L é livre de contexto e R é regular, então L\cap R é livre de contexto. Vamos usar a construção de um autômato de pilha (PDA) que simula em paralelo um PDA que reconhece L e um DFA que reconhece R.

Passo 2

Seja
M = (Q,\Sigma,\Gamma,\delta,q_0,Z_0,F)
um PDA que reconhece L, e seja
D = (P,\Sigma,\pi,p_0,A)
um DFA que reconhece R. Aqui Q é o conjunto de estados do PDA, \Gamma o alfabeto de pilha, \delta sua função de transição, e P é o conjunto de estados do DFA com função de transição \pi.

Passo 3

Definimos o PDA
M' = (Q',\Sigma,\Gamma,\delta',q'_0,Z_0,F')
que reconhecerá L\cap R da seguinte forma:
\displaystyle Q' = Q \times P,
\displaystyle q'_0 = (q_0,p_0),
\displaystyle F' = F \times A.
A ideia é que um estado (q,p) de M' indique “PDA em q” e “DFA em p”.

Passo 4

Precisamos definir \delta'. Para cada transição de M e cada estado p\in P:
1. Se
(q',\gamma)\;\in\;\delta\bigl(q,a,A\bigr)
com a\in\Sigma e A\in\Gamma, então em M' temos
\bigl((q',\,\pi(p,a)),\,\gamma\bigr)\;\in\;\delta'\bigl((q,p),\,a,\,A\bigr).
Aqui consumimos a na entrada, fazemos a mesma operação na pilha e avançamos o estado do DFA via \pi(p,a).
2. Se
(q',\gamma)\;\in\;\delta\bigl(q,\varepsilon,A\bigr),
então
\bigl((q',\,p),\,\gamma\bigr)\;\in\;\delta'\bigl((q,p),\,\varepsilon,\,A\bigr).
Ou seja, transições- \epsilon do PDA original ocorrem sem mudar o estado do DFA.
Dessa forma M' consome cada símbolo simulando ao mesmo tempo M e D.

Passo 5

Para provar correção, mostre duas implicações:
1. Se x é aceito por M', então há uma sequência de configurações que vai de \bigl((q_0,p_0),Z_0\bigr) a algum \bigl((q_f,p_f),\varepsilon\bigr) com (q_f,p_f)\in F'. Isso implica que q_f\in F e p_f\in A, ou seja, x\in L (pois M chega em q_f\in F) e x\in R (pois D chega em p_f\in A). Logo x\in L\cap R.
2. Se x\in L\cap R, então existe em M um caminho de (q_0,Z_0) a (q_f,\varepsilon) com q_f\in F e em D um caminho de p_0 a p_f\in A. Podemos intercalar passo a passo essas duas simulações para construir uma execução de M' que termina em \bigl((q_f,p_f),\varepsilon\bigr), provando que M' aceita x.
Assim L(M')=L\cap R, o que demonstra a correção da construção.

Resposta

O PDA que reconhece L\cap R é
M' = \bigl(Q\times P,\;\Sigma,\;\Gamma,\;\delta',\;(q_0,p_0),\;Z_0,\;F\times A\bigr)
com \delta' dada por
\begin{aligned} &\text{se }(q',\gamma)\in\delta(q,a,A)\text{ e }p\in P,\text{ então}\\\ &\quad\bigl((q',\pi(p,a)),\gamma\bigr)\;\in\;\delta'\bigl((q,p),a,A\bigr),\\\ &\text{se }(q',\gamma)\in\delta(q,\varepsilon,A)\text{ e }p\in P,\text{ então}\\\ &\quad\bigl((q',p),\gamma\bigr)\;\in\;\delta'\bigl((q,p),\varepsilon,A\bigr). \end{aligned}ãã
Os estados finais são F\times A.

Exercícios relacionados