Una gramática de línea recta (a veces abreviada como SLG) es una gramática formal que genera exactamente una cadena. [1] En consecuencia, no se bifurca (cada no terminal tiene solo una regla de producción asociada) ni bucle (si el no terminal A aparece en una derivación de B , entonces B no aparece en una derivación de A ). [1]
Áreas de utilidad
Las gramáticas de línea recta se utilizan ampliamente en el desarrollo de algoritmos que se ejecutan directamente en estructuras comprimidas (sin descompresión previa). [2] : 212
Los SLG son de interés en campos como la complejidad de Kolmogorov , la compresión de datos sin pérdida , el descubrimiento de estructuras y las estructuras de datos comprimidos . [ aclaración necesaria ]
El problema de encontrar una gramática libre de contexto (equivalentemente: una SLG) de tamaño mínimo que genere una cadena dada se denomina problema gramatical más pequeño . [ cita requerida ]
Las gramáticas de línea recta (más precisamente: gramáticas de cadena sin contexto de línea recta) se pueden generalizar a gramáticas de árbol sin contexto de línea recta . Este último puede usarse convenientemente para comprimir árboles . [2] : 212
Definicion formal
Una gramática libre de contexto G es una SLG si:
1. para cada N no terminal , hay como máximo una regla de producción que tiene a N como su lado izquierdo, y
2. el gráfico dirigido G = < V , E >, definido por V como el conjunto de no terminales y ( A , B ) ∈ E siempre que B aparece en el lado derecho de una regla de producción para A , es acíclico .
Una definición matemática del formalismo más general de las gramáticas de árbol libres de contexto de línea recta se puede encontrar en Lohrey et al. [2] : 215
Un SLG en la forma normal de Chomsky es equivalente a un programa de línea recta . [ cita requerida ]
Una lista de algoritmos que utilizan SLG
- El algoritmo de Sequitur construye una gramática en línea recta para una cadena determinada.
- El algoritmo Lempel-Ziv-Welch crea una gramática libre de contexto de una manera tan determinista que es necesario almacenar solo la regla de inicio de la gramática generada.
- Codificación de pares de bytes
Ver también
- Código basado en gramática
- Gramática no recursiva : una gramática que no se repite, pero que puede ramificarse; generando un lenguaje finito en lugar de un singleton
Referencias
- ^ a b Florian Benz y Timo Kötzing, "Una heurística eficaz para el problema gramatical más pequeño", Actas de la decimoquinta conferencia anual sobre la conferencia sobre cómputo genético y evolutivo - GECCO '13, 2013. ISBN 978-1-4503-1963-8 doi : 10.1145 / 2463372.2463441 , pág. 488
- ^ a b c Markus Lohrey; Sebastian Maneth; Manfred Schmidt-Schauß (2009). "Reducción de parámetros en árboles gramaticales comprimidos". Proc. FOSSACS (PDF) . LNCS. 5504 . Saltador. págs. 212-226.