Fecho das CFL para substituições e homomorfismos

Definição

Uma função \(h:\Sigma\to\Gamma^\star\) tal que \((\forall \sigma\in \Sigma)(h(\sigma)\text{ é uma CFL})\) diz-se uma substituição livre de contexto.

Teorema

Se \(L\) é uma CFL e \(h\) é uma substituição livre de contexto, então \(h(L)\) é também uma CFL.

Demonstração: Seja \(G=\langle V,\Sigma,P,z_0\rangle\) a gramática tal que \(\mathcal{L}(G)=L\) e para cada \(\sigma\in\Sigma\), seja \(G_\sigma=\langle V_\sigma,\Gamma,P_\Sigma,z_\sigma\rangle\) tal que \(\mathcal{L}(G_\sigma)=h(\sigma)\). Podemos supor, sem perda de generalidade que todas os conjuntos \(V\) e \(V_\sigma\) são disjuntos dois a dois. Então \(h(L)\) é gerada pela CFG \[G'=\left\langle V\cup\bigcup_{\sigma\in\Sigma}V_\sigma,\Gamma,P',z_0\right\rangle,\] em que \(P'\) contém todas as produções de todos \(P_\sigma\) mais todas as produções de \(P\) em que cada ocorrência de \(\sigma\) foi substituída por \(z_\sigma\). É trivial que esta gramática \(G'\) é tal que \(\mathcal{L}(G')=h(L)\).◻

Recorda que um homomorfismo é uma aplicação definida como a extensão natural de \(h:\Sigma\to\Gamma^\star\) a \(\Sigma^\star\), se \(|h(\sigma)|=1\), para todo o \(\sigma\in\Sigma\).

Teorema

As CFL são fechadas para a imagem directa e recíproca de homomorfismos.

Demonstração: Que as CFL são fechadas para a imagem de homomorfismos é consequência directa do teorema anterior, pois os homomorfismos são, trivialmente, substituições independentes de contexto.

Quanto à imagem reversa de homomorfismos o problema é mais delicado. Seja \(L=\mathcal{L}(A)\), com \(A\) um PDA, uma CFL com alfabeto \(\Gamma\) e \(h:\Sigma\to\Gamma^\star\) um homomorfismo. Poderíamos ser tentados a definir um autómato \(\mathcal{L}(A')=\mathcal{L}(h^{-1}(L))\) em \(\Sigma^\star\), como fizemos para o teorema equivalente para as linguagens regulares, e de cada vez que lemos um \(\sigma\), calcular \(h(\sigma)\) e obter o resultado em \(A\) para o transpor para \(A'\). Mas como se tratam de PDAs, a evolução da pilha de \(A\) quando este lê \(h(\sigma)\) (que tem potencialmente comprimento maior do que 1) pode não ser exprimível por uma só transição de \(A'\). Assim temos que guardar num “buffer” os caracteres de \(h(\sigma)\) para os podermos processar um de cada vez. Os PDAs não possuem memória para além da que podem simular no “controlo”, ou seja no conjunto de estados. Esta simulação de “memória” tem a limitação que tem que ser de uma dimensão constante, ou seja não pode depender do tamanho do input. Felizmente como \(\Sigma\) é finito, e cada imagem \(h(\sigma)\) é constituída por uma só palavra, o conjunto \[U=\bigcup_{\sigma\in\Sigma}\mathop{\mathrm{suff}}(h(\sigma))\] também é finito e portanto podemos simular o comportamento de um buffer no conjunto finito dos estados.

Suponhamos, então, que \[A=\langle Q,\Gamma,\Lambda,\delta,q_0,z_0,F\rangle.\] O novo PDA \(A'\) que vai gerar \(h^{-1}(L)\) será \[A'=\langle Q\times U, \Sigma,\Lambda,\delta',(q_0,\varepsilon),z_0,F'\rangle,\]com \[\begin{array}{ll} i)&\delta'((q,\varepsilon),\sigma,y)=\{((q, h(\sigma)),y), \forall y\in\Gamma,\forall q\in Q,\forall \sigma\in\Sigma\}\\ ii)&\delta'((q, x),\varepsilon,y)=\{((p, x,\gamma)\mid \delta(q,\varepsilon,y)\ni (p,\gamma)\},\\ iii)&\delta'((q,\sigma x),\varepsilon,y)=\{((p,x),\gamma)\mid \delta(q,\sigma, y)\ni (p,\gamma)\}, \end{array}\] e \(F'=F\times\{\varepsilon\}\).

Temos agora que mostrar que \(h^{-1}(\mathcal{L}(A))=\mathcal{L}(A').\) Primeiro observemos que se \(\alpha qh(\sigma)\Rightarrow^\star_A\beta p\) então, pela aplicação das regras i), ii) e iii) \[\alpha(q,\varepsilon)\sigma\Rightarrow_{A'}\alpha(q, h(\sigma))\Rightarrow^\star_{A'}\beta(p,\varepsilon).\] Portanto, se \(A\) aceita \(h(w)\), i.e., \[z_0q_0h(w)\Rightarrow^\star_A\beta p\] para algum \(p\in F\) e \(\beta\in \Lambda^\star\), então \[z_0(q_0,\varepsilon)w\Rightarrow^\star_{A'}\beta(p,\varepsilon)\] e, portanto \(A'\) aceita \(w\). Portanto \(\mathcal{L}(A')\supseteq h^{-1}(\mathcal{L}(A)).\)

Para a inclusão no sentido contrário, suponhamos que \(A'\) aceita \(w=\sigma_1\sigma_2\cdots\sigma_n\). Como a regra i) só pode ser aplicada quando o buffer está vazio, a sequência de movimentos que leva à aceitação de \(w\) tem que ser \[\begin{array}{ll} z_0(q_0,\varepsilon)\sigma_1\sigma_2\cdots\sigma_n&\Rightarrow^\star_{A'} \alpha_1(p_1,\varepsilon)\sigma_1\sigma_2\cdots\sigma_n,\\ &\Rightarrow_{A'}\alpha_1(p_1,h(\sigma_1))\sigma_2\sigma_3\cdots\sigma_n,\\ &\Rightarrow^\star_{A'}\alpha_2(p_2,\varepsilon)\sigma_2\sigma_3\cdots\sigma_n,\\ &\vdots\\ &\Rightarrow^\star_{A'}\alpha_n(p_{n-1},\varepsilon)\sigma_n,\\ &\Rightarrow_{A'}\alpha_n(p_{n-1},h(\sigma_n)),\\ &\Rightarrow^\star_{A'}\alpha_{n+1}(p_n,\varepsilon), \end{array}\] com \(p_n\in F\). As transições de \((p_i,\varepsilon)\) para \((p_{i+1},h(\sigma_i))\) faz-se pela regra i), as outras transições pelas regras ii) e iii). Portanto \(z_0q_0\Rightarrow^\star_A\alpha_1p_1\), e, para todo o \(i\), \[\alpha_ip_ih(\sigma_i)\Rightarrow^\star_A \alpha_{i+1}p_{i+1}.\] Tomando estes movimentos em conjunto, temos \[z_0q_0h(\sigma_1\sigma_2\cdots\sigma_n)\Rightarrow^\star_A \alpha_{n+1}p_n,\] portanto \(h(\sigma_1\sigma_2\cdots\sigma_n)\in \mathcal{L}(A)\). Portanto \(\mathcal{L}(A')\subseteq h^{-1}(\mathcal{L}(A))\). Portanto concluímos que \(\mathcal{L}(A')=h^{-1}(\mathcal{L}(A))\). ◻

Fecho das CFL para com a intersecção com linguagens regulares

Apesar das CFL não serem fechadas para a intersecção, são fechadas para a intersecção com linguagens regulares.

Teorema

seja \(L_1\) uma CFL e \(L_2\) uma linguagem regular, então \(L_1\cap L_2\) é uma CFL.

Demonstração: Seja \(A=\langle Q_1,\Sigma,\Gamma,\delta_1,q'_0,Z_0,F_1\rangle\) um PDA que represente a linguagem \(L_1\) e \(B=\langle Q_2,\Sigma,\delta_2,q''_2,F\rangle\) um DFA que represente a linguagem \(L_2\). Então \(L_1\cap L_2\) é reconhecida pelo seguinte PDA: \[\langle Q_1\times Q_2,\Sigma,\Gamma,\delta,(q'_0,q''_0),Z_0,F_1\times F_2\rangle,\] em que \[\delta((q_1,q_2),a,X)=\{((q'_1,q'_2),\alpha)\mid \delta_1(q_1,a,X)\ni (q'_1,\alpha)\land(\delta_1(q_2,a)=q'_2\}.\] A construção é a construção do autómato produto, já feita para demonstração que as linguagens regulares são fechadas para a intersecção, mas com o pormenor de se ter que preservar o funcionamento da pilha. O autómato resultante reconhece, trivialmente, a linguagem pretendida. ◻

Quociente de uma CFL por uma linguagem regular

Recordemos que, dadas duas linguagens \(L_1\) e \(L_2\) define-se \[L_1/L_2=\{x\mid \exists y\in L_2, xy\in L_1\}.\]

Teorema

Seja \(L_1\) uma CFL e \(L_2\) uma linguagem regular, então \(L_1/L_2\) é uma CFL.

Demonstração: Seja \(A=\langle Q_1,\Sigma,\Gamma,\delta_1,q'_0,Z_0,F_1\rangle\) um PDA que represente a linguagem \(L_1\) e \(B=\langle Q_2,\Sigma,\delta_2,q''_2,F\rangle\) um DFA que represente a linguagem \(L_2\). O PDA que reconhece este quociente tem que proceder em duas fases: numa primeira lê o input \(x\) e processa-o no PDA \(A\), e numa segunda tenta, especulativamente, encontrar palavras que possam estar em \(L_2\) e que concatenadas a \(x\) formem uma palavra de \(L_1\).

Assim um PDA que reconheça \(L_1/L_2\) é \[\langle Q_1\times(Q_2\cup\{\bot\}),\Sigma,\Gamma,\delta,(q'_0,\bot),Z_0,F_1\times F_2\rangle.\] A definição de \(\delta\) é a seguinte:

• As transições correspondentes à primeira fase são aquelas a que correspondem os estados da forma \((q_1,\bot)\). Assim para quaisquer \(q_1\in Q_1\), \(a\in \Sigma\cup\{\varepsilon\}\) e \(X\in \Gamma\) \[\delta((q_1,\bot),a,X)=\{((q_2,\bot),\alpha)\mid \delta_1(q_1,a,C)\ni (q_2,\alpha)\}.\]

• Em qualquer estado \((q_1,\bot)\) o input pode terminar e portanto têm que existir transições que passem para o funcionamento correspondente à segunda fase. Assim para todo o \(q\in Q_1\) e \(C\in\Gamma\) \[\delta((q,\bot),\varepsilon,C)\ni ((q,q''_0),C).\]

• Finalmente, na segunda fase, procuramos, não deterministicamente, palavras de \(y\in L_2\) que possam levar que \(xy\in L_1\). \[\delta((q_1,q_2),\varepsilon,X)=\{((q'_1,q'_2),\alpha\mid \delta_2(q_2,a)=q'_2\land \delta_1(q_1,a,X)\ni (q'_1,\alpha)\}.\]

Dada a a forma como foi construído o autómato, é trivial que este reconhece \(L_1/L_2\).◻