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 | editar código-fonte]
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[editar | editar código-fonte]
A gramática de prefixo
- Σ = {0, 1}
- S = {01, 10}
- P = {0 → 010, 10 → 100}
descreve a linguagem definida pela expressão regular
