Computação

GRAMATICA

Uma linguagem formal pode ser representada por uma gramática, isto é, um conjunto de regras de aceitação de cadeias.
A definição formal de uma gramática é uma quádrupla ordenada g (V,T,P,S), onde:
*V é o conjunto de símbolos não terminais
*T é o conjunto de simbolos terminais
*P é o conjunto de regras de producao
*S é o elemento de V, denominado símbolo inicial

A regras de producao são escritas na forma & -> B, onde & e B são compostos de não terminais e terminais. Alem disso, & possui pelo menos um não terminal.

Convenções
As seguintes convenções de notação são adotadas:
*Cada não terminal é representado por uma letra maiúscula do alfabeto português.
*Cada terminal é representado por apenas uma letra minuscula ou digito {0,1,2,3,4,....}
*Utiliza-se a própria letra maiúscula S para ser o símbolo inicial da gramática.
Ex1: Seja G a gramática:

S -> AB
A _> aA/a
B -> b Neste exemplo, a gramática possui 4 regras S -> AB, A ->aA, a -> a e B -> b

O símbolo “|” pode ser usado quando há mais de uma regra para um mesmo não terminal, como o não terminal “A” do exemplo.
O conjunto de não terminais para a gramática G é V={S,A,B}. O conjunto de terminais T={a,b}. O conjunto de regras P={S -> AB, A -> aA, A -> a, B -> b}. A seja “” indica que o não terminal a sua esquerda pode ser substituído pelo símbolo ou símbolos que estão a sua direita. Assim:
* O não terminal S pode ser substituído por AB
* O A aA ou por a
* O B b

As palavras ou cadeias validas na linguagem são formadas a partir do símbolo inicial, substituindo-o por alguma de suas regras e os não terminais desta sucessivamente, ate que se obtenham apenas terminais. Assim, utilizando, a gramática definida anteriormente, pode-se obter a palavra “aaab” efetuando-se seguintes substituições:

(1) AB
(2) aAB
(3) aaAb
(4) aaaB
(5) aaab

Na linha (1) foi