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 ramifica (cada no terminal tiene solo una regla de producción asociada) ni se repite (si el no terminal A aparece en una derivación de B , entonces B no aparece en una derivación de A ). [1]
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 de gramática más pequeña . [ cita requerida ]
Las gramáticas lineales (más precisamente: gramáticas lineales de cadenas libres de contexto) se pueden generalizar a gramáticas lineales de árboles libres de contexto . Estas últimas se pueden utilizar convenientemente para comprimir árboles . [2] : 212
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 N como su lado izquierdo, y
2. el grafo dirigido G =< V , E >, definido por V siendo 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 árboles libres de contexto de línea recta se puede encontrar en Lohrey et al. [2] : 215
Una SLG en forma normal de Chomsky es equivalente a un programa de línea recta . [ cita requerida ]