Introdução às gramáticas
A utilização de conjuntos para definir linguagens não é frequentemente a forma mais adequada e versátil para as descrever.
Preferível identificar estruturas intermédias, que abstraem partes ou subconjuntos importantes.
Descrições recursivas são bem mais simples, sem perda da objetividade e do rigor necessários.
As gramáticas descrevem linguagens por compreensão recorrendo a representações formais e (muitas vezes) recursivas.
As gramáticas definem formalmente as sequências válidas.
Exemplo
Para a frase:
"O cão ladra"
Temos uma gramática G
G = ({O, Um, cão, lobo, ladra, uiva}, {frase, sujeito, predicado, artigo, substantivo, verbo}, frase, P).
P tem as seguintes regras:
frase -> sujeito predicado
sujeito -> artigo substantivo
predicado -> verbo
artigo -> O | Um
substantivo -> cão | lobo
verbo -> ladra | uiva
Pode ser descrita na seguinte árvore
Gramática G = ({0,1}, {S,A}, S, P)
S -> 0S
S -> 0A
A -> 0A 1
A -> epsilon
A linguagem resultante será
Sendo A = {a, b}, a gramática será
A gramática G = ({a,b}, {S,X}, S,P), onde P terá as regras:
S -> aX
X -> aX
X -> bX
X -> epsilon
ou
S -> aX
X -> aX | bX | epsilon
Sendo A = {0, 1}, a gramática será
A gramática G = ({0,1}, {S,A}, {S,P}), onde P é constituído pelas regras:
S -> S 1 S 1 S | A
A -> 0 A | epsilon
Last updated