En informática teórica y teoría del lenguaje formal , una gramática de prefijos es un tipo de sistema de reescritura de cadenas , que consta de un conjunto de reglas de reescritura de cadenas , y es similar a una gramática formal o un sistema semi-Thue . Lo específico de las gramáticas de prefijos no es la forma de sus reglas, sino la forma en que se aplican: sólo se reescriben los prefijos . Las gramáticas de prefijos describen exactamente todos los lenguajes regulares . [1]
Una gramática de prefijo G es una tupla de 3 , (Σ, S , P ), donde
Para las cadenas x , y , escribimos x → G y (y decimos: G puede derivar y de x en un solo paso) si hay cadenas u, v, w tales que y v → w están en P. Tenga en cuenta que → G es una relación binaria en las cadenas de Σ.
El lenguaje de G , denotado , es el conjunto de cadenas derivables de S en cero o más pasos: formalmente, el conjunto de cadenas w tales que para algunas s en S , s R w , donde R es la clausura transitiva de → G.
La gramática del prefijo
describe el lenguaje definido por la expresión regular
