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