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 VN é 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

Exemplo

Vamos considerar a gramática -

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

Algumas das strings que podem ser derivadas são -

S ⇒ aA b usando produção S → aAb

⇒ a aA bb usando produção aA → aAb

⇒ aaa A bbb usando produção aA → aAb

⇒ aaabbb usando produção A → ε