Gramática linear

---

Seja $G=(V,T,P,S)$ uma gramática, com $A,B\in V$ e $w\in T^{\ast }$.

NOTE

$w\in T^{\ast }$ significa que $w$ é formada apenas por símbolos terminais (do conjunto $T$), podendo ter qualquer comprimento, inclusive ser a palavra vazia (por conta da definição de Fecho de Kleene sobre concatenação sucessivas).

Uma gramática $G$ é dita Gramática Linear (GL) quando todas as suas regras de produção seguem um formato que restringe a posição da variável (não terminal) em relação à sequência de terminais. Assim, temos as seguintes classificações:

• Gramática Linear à Direita (GLD): todas as regras são da forma: $A\to wB\text{ou}A\to w$ Ou seja, a variável $B$ (quando presente) aparece apenas à direita da sequência $w$.

• Gramática Linear à Esquerda (GLE): todas as regras são da forma: $A\to Bw\text{ou}A\to w$ Neste caso, a variável $B$ (quando presente) aparece apenas à esquerda da sequência $w$.

• Gramática Linear Unitária à Direita (GLUD): segue o mesmo formato da GLD, mas com a restrição de que o comprimento de $w$ é no máximo 1, ou seja: $|w|\le 1$

• Gramática Linear Unitária à Esquerda (GLUE): segue o mesmo formato da GLE, mas também com a restrição: $|w|\le 1$

TIP

Uma gramática é dita Gramática Regular (GR) quando é uma gramática linear, ou seja, qualquer gramática que se enquadre nos formatos GLD, GLE, GLUD ou GLUE é considerada regular.

Teorema

Seja $L$ uma linguagem. Então as seguintes afirmações são equivalentes:

1. $L$ é gerada por uma GLD.
2. $L$ é gerada por uma GLE.
3. $L$ é gerada por uma GLUD.
4. $L$ é gerada por uma GLUE.

Ou seja, todas as gramáticas lineares são equivalentes, independentemente da posição da variável nas regras de produção ou do comprimento de $w$.

EXAMPLE

A linguagem $a(ab{)}^{\ast }$ pode ser gerada por diferentes gramáticas lineares e regulares:

• GLD: $G=(S,A,a,b,P,S)$ com: $S\to aA$ $A\to baA\mid \epsilon$

• GLE: $G=(S,a,b,P,S)$ com: $S\to Sba\mid a$

• GLUD: $G=(S,A,B,a,b,P,S)$ com: $S\to aA$ $A\to bB\mid \epsilon$ $B\to aA$

• GLUE: $G=(S,A,a,b,P,S)$ com: $S\to Aa\mid a$ $A\to Sb$

Referências

---

Aula de Gramática Regular