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.M. Frazier and C. D. Page.
Definição formal 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 u → v 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 A gramática de prefixo Σ = {0, 1} S = {01, 10} P = {0 → 010, 10 → 100} descreve a linguagem definida pela expressão regular
Ver também Gramática regular
Referências
Categoria:Linguagens formais