Prefijo de gramática
En la informática teórica y la teoría del lenguaje formal , una gramática de prefijo 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: solo se reescriben los prefijos . Las gramáticas de prefijo describen exactamente todos los lenguajes regulares . [1]
Definicion formal
Un prefijo gramatical G es una tupla de 3 , (Σ, S , P ), donde
- Σ es un alfabeto finito
- S es un conjunto finito de cadenas base sobre Σ
- P es un conjunto finito de reglas de producción de la forma u → v donde u y v son cadenas sobre Σ
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 tal que , y v → w está 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 derivable de S en cero o más pasos: formalmente, el conjunto de cadenas w tal que para algunos s en S , s R w , donde R es el cierre transitivo de → G .
Ejemplo
El prefijo gramatical
- Σ = {0, 1}
- S = {01, 10}
- P = {0 → 010, 10 → 100}
describe el idioma definido por la expresión regular
Ver también
Referencias
