Aula 13

Gramáticas Independentes de Contexto (CFG)

Da mesma forma que estudamos diferentes representações formais para linguagens regulares, autómatos finitos e expressões regulares, para as CFL também vamos usar diferentes forma de representação. Uma outra forma (que iremos mostrar equivalente) de representar CFLs é a das Gramática Independentes de Contexto (CFG).

Definição

Uma gramática independente de contexto é um quadruplo \(\langle V,\Sigma, P, S\rangle,\) em que

• \(V\) é um conjunto finito chamado de conjunto das variáveis ou conjunto dos símbolos não terminais.

• \(\Sigma\) é o alfabeto da linguagem ou conjunto dos símbolos terminais, também finito.

• \(P\) é o conjunto (finito) de produções \[P\subseteq V\times (V\cup\Sigma)^\star;\]

• \(S\) (\(S\in V\)) é o símbolo inicial (ou de topo) da gramática.

Normalmente agrupam-se as produções com o mesmo símbolo não terminal como primeiro elemento da seguinte forma: em vez de escrever \[\{(U,\alpha_1),(U,\alpha_2),\cdots,(U,\alpha_n)\}\] escrevemos \[U\rightarrow\alpha_1\mid \alpha_2\mid\cdots\mid\alpha_n.\]

Dizemos que \(\alpha U\beta\Rightarrow_G \alpha\gamma\beta\), se em \(G\) existir uma produção \(U\rightarrow\gamma\). Assim, dizemos que \(w\) é aceite pela gramática \(G=\langle V,\Sigma,P,S\rangle\) se \(S\Rightarrow^\star w\). Portanto \[\mathcal{L}(G)=\{w\mid S\Rightarrow^\star w\}.\]

Exemplo

A seguinte gramática reconhece a linguagem \(\{a^nb^n\mid n\in\mathbb{N}\}\): \[\langle \{S\},\{a,b\},\{(S,aSb),(S,\varepsilon)\},S\rangle,\] ou seja \[S\rightarrow aSb\mid \varepsilon.\] Para a palavra \(aaabbb\) temos \[S\Rightarrow aSb\Rightarrow aaSbb\Rightarrow aaaSbbb\Rightarrow aaabbb.\] Portanto \(aaabbb\in \mathcal{L}(G)\).

Exemplo

A seguinte gramática \(G\) reconhece a linguagem \[L_2=\{w\in\{0,1,2\}^\star\mid |w|_0=|w|_1+|w|_2\}:\] \[S\rightarrow 0S1\mid 1S0\mid 0S2\mid 2S0\mid SS\mid \varepsilon.\] Demonstração: Primeiro mostremos que \(\mathcal{L}(G)\subseteq L_2\). Seja \(w\in \{0,1,2\}^\star\) tal que \(S\Rightarrow^\star w\), ou seja, \(\exists n\; S\Rightarrow^n w\). Então podemos mostrar por indução sobre \(n\) que \(w\in L_2\).

Se \(n=1\), então a única produção que pode ter sido usada é \(S\rightarrow\varepsilon\), porque é a única cuja componente direita não contém variáveis, e portanto \(w=\varepsilon\in L_2\).

Suponhamos agora que para todo o inteiro \(k<n\) e \(w\in\{0,1,2\}^\star\), se \(S\Rightarrow^k w\) então \(w\in L_2\). Basta, então, mostrar que se \(S\Rightarrow^n w\) também se tem que \(w\in L_2\).

Se \(S\Rightarrow^n w\) com \(n>1\) então a primeira produção usada não pode ser \(S\rightarrow\varepsilon\), portanto tem que ser uma das outras cinco. Se for uma das primeiras quatro, por exemplo \(S\rightarrow 0S1\), temos \[S\Rightarrow 0S1\Rightarrow ^{n-1}w.\] Portanto \[S\Rightarrow^{n-1}w'.\] Mas então, pela hipótese de indução, \(w'\in L_2\), o que é equivalente a dizer que \(|w'|_0=|w'|_1+|w'|_2\). Mas como \[w = 0w'1,\] isso implica que \[|w|_0=|w'|_0+1=|w'|_1+|w'|_2+1=|w|_1+|w|_2.\] Logo \(w\in L_2\). Para as outras três produções semelhantes a demonstração é exactamente a mesma.

Se a primeira produção usada for \(S\rightarrow SS\), isso significa que \[w=w'w''\text{ com } S\Rightarrow^{m'}w'\land S\Rightarrow^{m''}w''\land m'+m''=n-1.\] Portanto, mais uma vez aplicando a hipótese de indução, temos \[|w'|_0=|w'|_1+|w'|_2\land |w''|_0=|w''|_1+|w''|_2,\] pelo que \[w=w'w''\in L_2.\] Mostremos agora que para qualquer \(w\in L_2\) se tem \(S\Rightarrow^\star w\). Como \(|w|_0=|w|_1+|w|_2\) temos que \(|w|=2n\), para algum natural \(n\). Podemos, então, proceder por indução sobre \(n\).

Se \(n=0\), então \(w=\varepsilon\) e \(S\Rightarrow\varepsilon\). Suponhamos que para todas as palavras \(w\in L_2\) com \(|w|\leq 2n\) se tem \(S\Rightarrow^\star w\). Seja então \(w\in L_2\) com \(|w|=2n\). Há duas hipóteses a considerar. Se \(w\) tem como caracteres extremos de um lado um \(0\) e do outro um caracter diferente, então \[w = 0w'1\text{ (por exemplo)}\] com \(w'\in L_2\) e \(|w'|=2n-2\). Então por hipótese de indução \(S\Rightarrow^\star w'\) e como \(0w'1=w\) temos \(S\Rightarrow0S1\Rightarrow^\star0w'1=w\). Se pelo contrário \(w\) começa e acaba com o caracter \(0\) (a demonstração é idêntica se começa e acaba com um caracter não \(0\)) então consideremos o seguinte. Seja \(w=w_1w_2\cdots w_{2n}\) e consideremos a seguinte função \(f:\{1,\ldots,2n\}\rightarrow \mathbb{N}\), com \(f(k)=2|w_1\cdots w_k|_0-k\). A função \(f\) corresponde à diferença do número dos caracteres \(0\) até à posição \(k\) e do correspondente número de caracteres não \(0\). Como estamos a supor que \(w\) começa e acaba em \(0\), temos \(f(1)=1\). Mas, da mesma forma, como \(w\in L_2\), portanto \(f(2n)=0\), temos que ter \(f(2n-1) = -1\). Portanto em algum ponto intermédio a função deve ter valor nulo. Ou seja \(w\) tem que se poder escrever como concatenação de duas palavras não nulas, \(w'\) e \(w''\), tais que \(w=w'w''\) com \(w',w''\in L_2\). Como \(|w|=|w'|+|w''|\), estas duas palavras têm tamanho menor que \(2n\) pelo que podemos aplicar a hipótese de indução, garantindo que \[S\Rightarrow^\star w'\land S\Rightarrow^\star w''.\]Portanto \[S\Rightarrow SS\Rightarrow^\star w'w''=w.\]◻

Teorema

As CFL são fechadas para:

• a união;

• a concatenação;

• o fecho de Kleene;

• a reversão.

Demonstração: Sejam \(L_1=\mathcal{L}(G_1)\) e \(L_2=\mathcal{L}(G_2)\), com \(G_1=\langle V_1,\Sigma,P_1,S_1\rangle\) e \(G_2=\langle V_2,\Sigma,P_2,S_2\rangle\), suponhamos ainda que \(V_1\cap V_2=\emptyset\) e \(S\notin V_1\cup V_2\).

\(L_1\cup L_2=\mathcal{L}(G)\), com \(G=\langle V_1\cup V_2\cup\{S\},\Sigma,P_1\cup P_2\cup\{S\rightarrow S_1\mid S_2\},S\rangle\).

\(L_1L_2=\mathcal{L}(G)\) com \(G=\langle V_1\cup V_2\cup\{S\},\Sigma,P_1\cup P_2\cup\{S\rightarrow S_1S_2\},S\rangle\).

\(L_1^\star=\mathcal{L}(G)\) com \(G=\langle V_1\cup\{S\},\Sigma,P_1\cup\{S\rightarrow S_1S\mid \varepsilon\},S\}\).

Seja \(P^R_1\) o conjunto de produções que se obtêm de \(P_1\) do seguinte modo: se em \(P_1\) constam as produções em \(U\), \(U\rightarrow \alpha_1\mid \alpha_2\mid\cdots\mid\alpha_n\), em \(P^R_1\) passam a constar as produções \(U\rightarrow \alpha^R_1\mid \alpha^R_2\mid\cdots\mid\alpha^R_n\). Então \(L_1^R=\mathcal{L}(G)\) com \(G=\langle V_1,\Sigma,P^R_1,S_1\rangle\). ◻

A classe das linguagens regulares está contida na classe das linguagens independentes de contexto. A escrita de uma CFG (linear à direita) que simule o comportamento de um DFA é muito simples. Um exemplo ilustra bem este método. Consideremos \(L\) a linguagem definida pelo seguinte DFA

A gramática que simula este autómato é dada por \[\begin{array}{l} Q\rightarrow 0Q\mid 1S\\ S\rightarrow 0S\mid 1Q\mid \varepsilon. \end{array}\]

Assim se temos um DFA \(\langle Q,\Sigma,\delta,q_0,F\rangle\), construímos uma gramática \(\langle Q,\Sigma,P,q_0\rangle\) em que o conjunto de variáveis é o conjunto de estados do DFA, o símbolo inicial é o estado inicial do autómato e cuja produções, para cada estado são \[q\rightarrow aq',\] se \(\delta(q,a)=q'\). No caso de \(q\in F\) acrescenta-se a produção \[q\rightarrow \varepsilon.\]