Next: Classificação
Up: Gramáticas
Previous: Terminologia
  Sumário
Formalmente, a definição de uma linguagem é uma quádrupla
onde
- é um alfabeto cujos símbolos são conhecidos como
símbolos terminais;
- é um alfabeto de símbolos não-terminais, sendo que
e
,
onde é o conjunto de símbolos da linguagem;
- é um conjunto de regras ou produções,
normalmente expressos na forma
, onde
e
. Normalmente,
é denominado o lado esquerdo da produção e , o
lado direito.
- é 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 para a linguagem pode ser formalmente descrita por
Cada string que pode ser derivada a partir do símbolo sentencial é
denominada uma forma sentencial. Por exemplo, em
as strings
são formas sentenciais.
Uma sentença é uma forma sentencial sem símbolos
não-terminais, como .
Uma forma sentencial de uma gramática é dita ser derivável
de outra forma sentencial ,
quando pode ser obtida a partir de a partir da
aplicação de uma ou mais produções de . Quando está claro a qual
gramática a derivação se refere, a indicação da gramática pode ser omitida,
Assim, no exemplo acima pode-se afirmar que
.
Similarmente, quando permite derivar por zero ou mais
aplicações de produções de uma gramática, pode-se expressar este
relacionamento por
onde a gramática a que se refere a derivação pode ser explicitada, se
preciso,
No exemplo,
e
.
Quando a forma sentencial de é obtida de pela
aplicação de exatamente uma produção, então diz-se que é
imediatamente derivável de ,
ou omitindo a gramática,
No exemplo,
e
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: Classificação
Up: Gramáticas
Previous: Terminologia
  Sumário
Ivan L. M. Ricarte
2003-02-14