Definição formal

Formalmente, a definição de uma linguagem é uma quádrupla $(V_T, V_N, P, S)$ onde

$V_T$

é um alfabeto cujos símbolos são conhecidos como símbolos terminais;

$V_N$

é um alfabeto de símbolos não-terminais, sendo que $V_T \cap V_N = \emptyset$ e $V_T \cup V_N = V$, onde $V$ é o conjunto de símbolos da linguagem;

$P$

é um conjunto de regras ou produções, normalmente expressos na forma $\alpha \rightarrow \beta$, onde $\alpha \in V^+$ e $\beta \in V^\ast$. Normalmente, $\alpha$ é denominado o lado esquerdo da produção e $\beta$, o lado direito.

$S \in V_N$

é o ponto de partida na produção de qualquer sentença na linguagem, denominado símbolo sentencial, símbolo não-terminal inicial ou simplesmente axioma.

A gramática $G_L$ para a linguagem $L$ pode ser formalmente descrita por

$$G_L = (\{0,1\}, \{S\}, P, S)$$
onde

$$P = \{S \rightarrow 0S1, S \rightarrow \varepsilon\}$$

Cada string que pode ser derivada a partir do símbolo sentencial é denominada uma forma sentencial. Por exemplo, em

$$S \Longrightarrow 0S1 \Longrightarrow 00S11 \Longrightarrow 000S111 \Longrightarrow 000111$$

as strings $0S1, 000S111, 000111$ são formas sentenciais. Uma sentença é uma forma sentencial sem símbolos não-terminais, como $000111$.

Uma forma sentencial $\delta$ de uma gramática $G$ é dita ser derivável de outra forma sentencial $\gamma$,

$$\gamma \overset{+}{\underset{G}{\Longrightarrow}} \delta$$

quando $\delta$ pode ser obtida a partir de $\gamma$ a partir da aplicação de uma ou mais produções de $G$. Quando está claro a qual gramática a derivação se refere, a indicação da gramática pode ser omitida,

$$\gamma \overset{+}{\Longrightarrow} \delta$$

Assim, no exemplo acima pode-se afirmar que $0 S 1 \overset{+}{\Longrightarrow} 000S111$.

Similarmente, quando $\gamma$ permite derivar $\delta$ por zero ou mais aplicações de produções de uma gramática, pode-se expressar este relacionamento por

$$\gamma \overset{*}{\Longrightarrow} \delta$$

onde a gramática a que se refere a derivação pode ser explicitada, se preciso,

$$\gamma \overset{*}{\underset{G}{\Longrightarrow}} \delta$$

No exemplo, $0 S 1 \overset{*}{\Longrightarrow} 000S111$ e $0 S 1 \overset{*}{\Longrightarrow} 0S1$.

Quando a forma sentencial $\delta$ de $G$ é obtida de $\gamma$ pela aplicação de exatamente uma produção, então diz-se que $\delta$ é imediatamente derivável de $\gamma$,

$$\gamma \underset{G}{\Longrightarrow} \delta$$

ou omitindo a gramática,

$$\gamma \Longrightarrow \delta$$

No exemplo, $0 S 1 \Longrightarrow 0 0 S 1 1$ e $0 0 0 S 1 1 1 \Longrightarrow 000111$

Em geral, buscar-se-á denotar símbolos terminais por strings de letras minúsculas e símbolos não-terminais por strings de letras maiúsculas. Formas sentenciais serão representadas por letras gregas.

Uma mesma linguagem pode ser gerada por mais de uma gramática. Quando duas gramáticas geram a mesma linguagem diz-se que elas são equivalentes.