Gramática de Prefixo

Na Ciência da computação teórica e na teoria das linguagens formais, uma gramática de prefixo é um tipo de sistema de reescrita de cadeias que consiste de um conjunto Sistema de redução de cadeias, e similar a uma Gramática formal ou um Sistemas de Thue-Semi. O que é particular em relação as gramáticas de prefixo não é a forma das suas regras, mas a maneira em que elas são aplicadas: apenas os prefixos são reescritos. As gramáticas de prefixo descrevem exatamente todas as linguagens regulares.[1]

Definição formal

editar

Uma gramática de prefixo G é uma tripla, (Σ, S, P), onde

  • Σ é um alfabeto finito
  • S é um conjunto finito de cadeias base sobre Σ
  • P é um conjunto de regras de produção na forma uv onde u and v são cadeias sobre Σ

Para cadeias x, y, escrevemos x →G y (e dizemos que: G pode derivar de y para x em um passo) se existem cadeias u, v, w tais que x = vu, y = wu, e v → w está em P. Note que G é uma Relação binária nas cadeias de Σ.

A linguagem de G, indicada por L(G), é o conjunto de cadeias deriváveis de S em zero ou mais passos: formalmente, o conjunto de cadeias w tais que para algum s em S, s R w, onde R é o Fecho transitivo de G.

Exemplo

editar

A gramática de prefixo

  • Σ = {0, 1}
  • S = {01, 10}
  • P = {0 → 010, 10 → 100}

descreve a linguagem definida pela expressão regular

 

Veja também

editar

Referências

editar