Classificação

Pelo exemplo que foi apresentado acima pode parecer que o lado esquerdo de produções de uma gramática está restrito a um único símbolo não-terminal. Entretanto, da definição de gramáticas deve estar claro que este não é o caso, pois em uma produção

$$\alpha \rightarrow \beta$$

definiu-se que $\alpha \in V^+$ e $\beta \in V^\ast$.

Assim, a gramática $G_1 = (\{a\},\{S,N,Q,R\},P,S)$, onde os elementos de $P$ são

$$S \rightarrow QNQ$$

$$QN \rightarrow QR$$

$$RN \rightarrow NNR$$

$$RQ \rightarrow NNQ$$

$$N \rightarrow a$$

$$Q \rightarrow \varepsilon$$

é uma gramática perfeitamente válida, gerando sentenças na linguagem $\{a^{2^n} \mid n \geq 0\}$. Derivações típicas incluem

$$S \Rightarrow QNQ \overset{+}{\Rightarrow} a$$

$$S \Rightarrow QNQ \Rightarrow QRQ \Rightarrow QNNQ \overset{+}{\Rightarrow} aa$$

Restringindo o tipo de produções que podem aparecer em uma gramática, é possível definir classes especiais de gramáticas, tal como proposto na hierarquia de Chomsky descrita a seguir.

Uma gramática definida sem restrições quanto ao tipo de produções que ela pode conter é dita ser uma gramática de tipo 0.

Uma gramática de tipo 1 obedece à propriedade $\mid\alpha\mid \leq \mid\beta\mid$ para todas as produções da forma $\alpha \rightarrow \beta$, onde $\mid\alpha\mid$ denota o comprimento (ou número de símbolos) em $\alpha$ e similarmente para $\mid\beta\mid$. Gramáticas de tipo 1 são também denominadas gramáticas sensíveis ao contexto.

Se a uma gramática de tipo 1 impõe-se a restrição adicional de que todos os lados esquerdos de produções tenham um único símbolo não-terminal, ou seja, $\mid\alpha\mid = 1$ para todas produções $\alpha \rightarrow \beta$ da gramática, então diz-se que a gramática é de tipo 2. Gramáticas de tipo 2 são também denominadas gramáticas livres de contexto.

Gramáticas de tipo 3 ou gramáticas regulares são gramáticas de tipo 2 onde as produções são apenas da forma

$$A \rightarrow a$$

$$A \rightarrow aA$$

quando a gramática é linear direita, ou da forma

$$A \rightarrow a$$

$$A \rightarrow Aa$$

quando a gramática é linear esquerda.

Por simplicidade de notação, quando um lado esquerdo de uma produção pode levar a duas (ou mais) formas sentenciais distintas no lado direito, pode-se representar estas regras de forma compacta usando o símbolo $\mid$, lido ou, como em $A \rightarrow a \mid aA$ ou $A \rightarrow a \mid Aa$ correspondendo aos exemplos de gramáticas lineares direita e esquerda, respectivamente.

À hierarquia de gramáticas corresponde uma hierarquia de linguagens. Assim, se uma linguagem pode ser gerada por uma gramática de tipo 3 ela é dita ser uma linguagem de tipo 3.