next up previous contents
Next: Classificação Up: Gramáticas Previous: Terminologia   Sumário

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

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

onde


$\displaystyle P$ $\displaystyle = \{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

$\displaystyle 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$,

$\displaystyle \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,

$\displaystyle \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

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

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

$\displaystyle \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$,

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

ou omitindo a gramática,

$\displaystyle \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.


next up previous contents
Next: Classificação Up: Gramáticas Previous: Terminologia   Sumário
Ivan L. M. Ricarte 2003-02-14