0. Gramatica Irrestrita

Uma gramática é dita irrestrita (Tipo 0) quando suas produções seguem a forma:

$$P = \lbrace \alpha \rightarrow \beta \ \Big| \ \alpha, \beta \in (V \cup \Sigma)^{*} \rbrace$$

onde:

  • $\alpha$ deve conter pelo menos um símbolo pertencente a $V$ (um símbolo não terminal).
  • $\beta$ pertence ao conjunto $(V \cup \Sigma)^{*}$, ou seja, pode ser qualquer sequência de símbolos terminais e não terminais.

1. Gramática Sensível ao Contexto (Tipo 1)

Uma gramática é dita sensível ao contexto quando suas produções seguem a forma:

$$P = \lbrace \alpha \rightarrow \beta \ \Big| \ \alpha, \beta \in (V \cup \Sigma)^{*},\ |\beta| \geq |\alpha| \rbrace$$

com a única exceção sendo a regra $S \to \epsilon$, desde que $S$ não apareça em nenhuma derivação.

2. Gramática Livre de Contexto (Tipo 2)

Uma gramática é dita livre de contexto quando suas produções seguem a forma:

$$P = \lbrace A \rightarrow \beta \ \Big| \ A \in V , \ \beta \in (V \cup \Sigma)^{+} \rbrace$$ Ou seja:

  • O lado esquerdo da produção deve ser um único símbolo não terminal $A$.
  • O lado direito $\beta$ pode conter qualquer sequência não vazia de símbolos terminais e/ou não terminais.

3. Gramática Regular (Tipo 3)

Uma gramática é dita regular quando suas produções seguem um dos seguintes formatos:

$$P = \lbrace A \rightarrow a, \quad A \rightarrow aB, \quad A \rightarrow Ba \ \Big| \ a \in \Sigma, \ A, B \in V \rbrace$$

Ou seja:

  • As regras devem ter um único não terminal no lado esquerdo.
  • No lado direito, as regras podem ser:
    • Forma direita: $A \rightarrow aB$ (não terminal à direita).
    • Forma esquerda: $A\rightarrow Ba$ (não terminal à esquerda).
    • Transição terminal: $A \rightarrow a$.

Se a gramática segue apenas a forma $A \to aB$ ou $A \to a$, ela é chamada regular à direita. Se a gramática segue apenas $A \to Ba$ ou $A \to a$, ela é chamada regular à esquerda.