Gramáticas Irrestritas

Prévia do material em texto

7 Linguagens Recursivamente Enumeráveis 351
A aplicação da produção S → aAbc, seguida de n aplicações da produção A → aAbC e,
finalmente, da aplicação da produção A → ǫ, gera uma forma sentencial do tipo an+1(bC )nbc. A
transposição dos símbolos “b” para o lado esquerdo, junto aos símbolos “a”, é feita com o auxílio
da produção Cb → bC . Após a aplicação dessa produção n + 1 vezes, chega-se à forma sentencial
an+1bn+1C nc. Finalmente, a aplicação da produção Cc → cc por n vezes substitui os não-terminais
“C ” pelos terminais “c” correspondentes, conduzindo à geração da sentença an+1bn+1cn+1. 2
Exemplo 7.4 A gramática G = ({S ,B ,X , a, b}, {a, b},P ,S), com P :
{S → aBSa | aBXa
Ba → aB
BX → Xb
aX → a}
gera a linguagem aibiai , i ≥ 1. A produção aX → a caracteriza esta gramática como sendo
irrestrita, uma vez que | aX |>| a |.
As duas produções iniciais geram formas sentenciais do tipo (aB)nXan . A partir desse ponto,
a aplicação repetida da produção Ba → aB permite obter formas sentenciais do tipo anBnXan .
Resta, portanto, substituir os símbolos não-terminais “B ” por terminais “b” para gerar as sentenças
pretendidas, tarefa esta que é cumprida pelas três últimas produções. O não-terminal “X ” serve
como delimitador, separando as cadeias à sua esquerda e à sua direita. Ele é usado, inicialmente,
como referência para substituir os símbolos “B ” por “b” e, finalmente, para se auto-remover da forma
sentencial, gerando anbnan . Exemplos de derivação:
• S ⇒ aBXa ⇒ aXba ⇒ aba
• S ⇒ aBSa ⇒ aBaBSaa ⇒ aBaBaBXaaa ⇒ aaBBaBXaaa ⇒ aaBaBBXaaa ⇒
aaaBBBXaaa ⇒ aaaBBXbaaa ⇒ aaaBXbbaaa ⇒ aaaXbbbaaa ⇒ aaabbbaaa
2
7.4 Forma Normal para Gramáticas Irrestritas
Devido ao fato de as gramáticas regulares, livres de contexto e sensíveis ao contexto cons-
tituírem casos particulares das gramáticas irrestritas, a forma normal que será apresen-
tada a seguir pode ser aplicada indistintamente em qualquer tipo de gramática examinada
até o momento.
A demonstração do teorema seguinte baseia-se na demonstração de [55], que por
sua vez é uma generalização da forma conhecida como Forma Normal de Kuroda para
gramáticas sensíveis ao contexto (ver Seção 5.3).
Teorema 7.3 (Forma normal para gramáticas irrestritas) Toda gramática irres-
trita G1 = (V1,Σ,P1,S ) define uma linguagem L que também pode ser gerada por uma
outra gramática G2 = (V2,Σ,P2,S ), equivalente, cujas produções são todas das seguin-
tes formas: (1) S → ǫ; (2) A → σ; (3) A → B; (4) A → BC; (5) AB → AC; (6)
AB → CB; (7) AB → C, onde S ,A,B ,C ∈ N2 e σ ∈ Σ.
Justificativa Conforme o Algoritmo 7.4, descrito a seguir, o qual incorpora as seguin-
tes etapas:
i. Eliminação das produções vazias;
ii. Incorporação da produção (1), caso a cadeia vazia faça parte da linguagem;
iii. Substituição dos símbolos terminais por novos símbolos não-terminais e incorpo-
ração de novas produções da forma (2), uma para cada símbolo terminal de G1;
352 Linguagens Formais - Teoria, Modelagem e Implementação
iv. Substituição das produções α → β, em que |α| ≤ |β|, por um novo conjunto de
produções das formas (3), (4), (5), (6) e (7);
v. Substituição das produções α → β, em que |α| > |β|, por um novo conjunto de
produções das formas (3), (4), (5), (6) e (7).
Algoritmo 7.4 (Forma normal para gramáticas irrestritas) Obtenção de uma gra-
mática irrestrita na forma normal.
• Entrada: uma gramática irrestrita G1 = (V1,Σ,P1,S );
• Saída: uma gramática irrestrita G2 = (V2,Σ,P2,S ), na forma normal, e tal que
L(G2) = L(G1);
• Método:
1. Início:
Sendo N1 = V1 − Σ e N2 = V2 − Σ, faz-se:
– N2 ← N1
– P2 ← ∅
2. Etapa (i):
Eliminam-se as produções da forma A→ ǫ contidas em P1:
– P2 ← P2 ∪ {XA→ X ,AX → X , σA→ σ,Aσ → σ | A→ ǫ ∈ P1,X ∈
N1, σ ∈ Σ}
3. Etapa (ii):
Incorporação da cadeia vazia, se for o caso:
– P2 ← P2 ∪ {S → ǫ, se ǫ ∈ L(G1)}
4. Etapa (iii):
Eliminação dos terminais originais e sua substituição por não-terminais cor-
respondentes:
– N2 ← N2 ∪ {Xσ, σ ∈ Σ}
– P2 ← P2 ∪{Xσ → σ, α1Xσα2 → β | α1σα2 → β ∈ P1, σ ∈ Σ, α1, α2 ∈
V ∗
1 }
– P2 ← P2 ∪ {Xσ → σ, α → β1σβ2 | α → β1σβ2 ∈ P1, σ ∈ Σ, β1, β2 ∈
V ∗
1 }
5. Etapa (iv):
Eliminação das produções α→ β, |α| ≤ |β|: