¿Por qué los autómatas lineales no son tan populares como otros autómatas?

En mi experiencia, los lenguajes sensibles al contexto y los autómatas lineales limitados son frecuentemente omitidos o ignorados en los cursos de teoría de la computabilidad, e incluso quedan fuera de algunos libros de texto notables, aunque los autómatas finitos y pushdown reciben mucha atención. ¿Seguramente debe haber una buena razón por la cual los LBA reciben menos atención que sus contrapartes?

Con modificaciones "apropiadas" podemos convertir estas clases en clases de complejidad; Autómatas finitos en , CFL en LogCFL y LBA en PSPACE.$NC^1$

Ahora debería quedar bastante claro por qué estamos interesados ​​en los dos primeros más que en LBA. Los dos primeros encajan naturalmente en la definición habitual de computación factible. Pero PSPACE no lo hace.

Bueno, pregúntale a tu profesor por qué lo hizo. Solo puedo adivinar.

No son tan interesantes como los modelos completos de Turing y el PDA porque están en el vacío de la inutilidad * que comparten, por supuesto, con su equivalente en el lenguaje: no tan poderoso como sea posible, pero ya muy intratable.

Otra razón podría ser que no se sabe tanto (adivinar aquí) sobre ellos, pero eso podría deberse a un problema de huevo de gallina.

No está claro el clima , por lo que podría plantear problemas para la didáctica. Además, las pruebas típicas (por ejemplo, lenguaje aceptado, equivalencias de modelos) son mucho más difíciles que para otros modelos.$NLBA = DLBA$

(*) exageración deliberada

Parece que no solo CSG sino también CFG, ... están pasados ​​de moda en estos días. Creo que en estos días los autómatas y PDA generalmente se piensan en cursos de teoría de computabilidad / complejidad (si es que los hay) y allí se incluyen no por su propio bien sino para introducir las máquinas de Turing.

Las gramáticas son probablemente interesantes para la teoría del compilador, pero no tanto para la computabilidad / complejidad que se incluirá en un curso introductorio de pregrado. Hay muchos temas que uno quisiera cubrir, pero un curso de un semestre es demasiado corto y tenemos que seleccionar y muchos de estos temas que no podemos cubrir debido a restricciones de tiempo son mucho más interesantes que LBA.

Las expresiones regulares y los CFG se utilizan en la práctica para analizar el código (es decir, los lenguajes de programación). La razón es que existen algoritmos muy eficientes para analizarlos. Los LBA, por otro lado, son demasiado poderosos para usar realmente en ese contexto.

Un origen histórico de la teoría de autómatas es el tema de la construcción del compilador. Por la razón mencionada anteriormente, solo los lenguajes regulares y los CFG son útiles para construir compiladores (a pesar del hecho de que las gramáticas atributivas no son realmente CFG, y que los algoritmos de análisis de CFG realmente no analizan toda la clase de CFG). Los LBA podrían haber sido inventados por Chomsky como un nivel intermedio de complejidad entre lo mundano y el "inglés". ¡Quizás el lugar apropiado para enseñarles es en cursos de lingüística en lugar de cursos de informática!