Gramática linear §

---

Seja uma gramática, com e .

Note

significa que é formada apenas por símbolos terminais (do conjunto ), 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 é 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: Ou seja, a variável (quando presente) aparece apenas à direita da sequência .

• Gramática Linear à Esquerda (GLE): todas as regras são da forma: Neste caso, a variável (quando presente) aparece apenas à esquerda da sequência .

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

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

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 uma linguagem. Então as seguintes afirmações são equivalentes:

1. é gerada por uma GLD.
2. é gerada por uma GLE.
3. é gerada por uma GLUD.
4. é 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 .

Example

A linguagem pode ser gerada por diferentes gramáticas lineares e regulares:

• GLD: com:

• GLE: com:

• GLUD: com:

• GLUE: com:

Referências §

---

Aula de Gramática Regular