Gramática linear

Considerando a gramática G = (V, $\Sigma$, P, S) onde :

• V={S, A, B}
  • A: elemento de V
  • B: elemento de V
• $\Sigma$: Alfabeto

Pode ser classificada em:

Gramática Linear à Direita (GLD)

Todas as regras de produção P seguem a forma:

• A$\to$wB
• A$\to$w

Gramática Linear à Esquerda(GLE)

Todas as regras de produção P seguem a forma:

• A$\to$Bw
• A$\to$w

Gramática Linear Unitária à Direita (GLUD)

Todas as regras de produção P seguem a forma:

• A$\to$wB
• A$\to$w
• |w| $\leq \;$ 1

Gramática Linear Unitária à Esquerda (GLUE)

Todas as regras de produção P seguem a forma:

• A$\to$Bw
• A$\to$w
• |w| $\leq \;$ 1