Introdução às Gramáticas

No sentido literário do termo, gramáticas denotam regras sintáticas para conversação em línguas naturais. A linguística tem tentado definir gramáticas desde o início das línguas naturais como o inglês, sânscrito, mandarim, etc.

A teoria das linguagens formais encontra sua aplicabilidade extensivamente nos campos da Ciência da Computação. Noam Chomsky deu um modelo matemático de gramática em 1956 que é eficaz para escrever linguagens de computador.

Gramática

Uma gramática G pode ser formalmente escrito como uma tupla de 4 (N, T, S, P) onde -

N ou V_N é um conjunto de variáveis ou símbolos não terminais.
T ou ∑ é um conjunto de símbolos de Terminal.
S é uma variável especial chamada símbolo inicial, S ∈ N
Psão as regras de produção para terminais e não terminais. Uma regra de produção tem a forma α → β, onde α e β são cordas em V _N ∪ Σ e pelo menos um símbolo de α pertence a V _N .

Exemplo

Grammar G1 -

({S, A, B}, {a, b}, S, {S → AB, A → a, B → b})

Aqui,

S, A, e B são símbolos não terminais;
a e b são símbolos terminais
S é o símbolo de início, S ∈ N
Produções, P : S → AB, A → a, B → b

Exemplo

Grammar G2 -

(({S, A}, {a, b}, S, {S → aAb, aA → aaAb, A → ε})

Aqui,

S e A são símbolos não terminais.
a e b são símbolos terminais.
ε é uma string vazia.
S é o símbolo de início, S ∈ N
Produção P : S → aAb, aA → aaAb, A → ε

Derivações de uma gramática

Strings podem ser derivadas de outras strings usando as produções em uma gramática. Se uma gramáticaG tem uma produção α → β, Nós podemos dizer que x α y deriva x β y no G. Esta derivação é escrita como -

x α y ⇒G x β y