Gramática de prefijos
La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 16 de diciembre de 2014; las comprobaciones requieren 3 ediciones .En informática, una gramática de prefijos es un tipo de sistema de reescritura de cadenas que consiste en un conjunto de reglas de reescritura de cadenas, similar a las gramáticas formales. Lo característico de una gramática de prefijos no es la forma de las reglas, sino la forma en que se aplican: sólo se reescriben los prefijos .
Formal definición
El prefijo gramatical G es el triple (Σ, S , P ), donde
- Σ es el alfabeto final
- S es un conjunto finito de filas básicas sobre Σ
- P es un conjunto de reglas de inferencia en la forma u → v , donde u y v son filas sobre Σ
Para cadenas x , y , x → G y (léase: G deriva y de x en un solo paso) es cierto si hay cadenas u, v, w tales que x = vu, y = wu y v → w pertenece a P . Tenga en cuenta que → G es una relación binaria en filas sobre Σ.
El lenguaje G , denotado L(G) , es el conjunto de cadenas que se pueden derivar de S en cero o más pasos. Formalmente, este es el conjunto de cadenas w tal que para alguna s de S tenemos s R w , donde R es la clausura transitiva → G .
Ejemplo
Gramática de prefijos
- Σ = {0, 1}
- S = {01, 10}
- PAG = {0 → 010, 10 → 100}
describe el lenguaje especificado por la expresión regular
Propiedades
Las gramáticas de prefijos describen exactamente todos los lenguajes regulares. [una]