¿Está desactualizada la jerarquía de Chomsky?

45

La jerarquía de Chomsky (–Schützenberger) se usa en los libros de texto de informática teórica, pero obviamente solo cubre una fracción muy pequeña de lenguajes formales (REG, CFL, CSL, RE) en comparación con el Diagrama completo del zoológico de complejidad . ¿La jerarquía juega algún papel en la investigación actual? Encontré pocas referencias a Chomsky aquí en cstheory.stackexchange, y en Complexity Zoo no se mencionan en absoluto los nombres de Chomsky y Schützenberger.

¿La investigación actual está más centrada en otros medios de descripción que las gramáticas formales? Estaba buscando métodos prácticos para describir lenguajes formales con diferente expresividad, y me topé con un lenguaje sensible al contexto creciente (GCSL) y lenguajes visiblemente pushdown (VPL), que se encuentran entre los idiomas clásicos de Chomsky. ¿No debería actualizarse la jerarquía de Chomsky para incluirlos? ¿O no tiene sentido seleccionar una jerarquía específica del conjunto completo de clases de complejidad? Intenté seleccionar solo aquellos idiomas que pueden encajar en los huecos de la jerarquía de Chomsky, por lo que entiendo:

REG (= Chomsky 3) ⊊ VPL ⊊ DCFL ⊊ CFL (= Chomsky 2) ⊊ GCSL ⊊ CSL (= Chomsky 1) ⊊ R ⊊ RE

Todavía no entiendo dónde encajan los "lenguajes ligeramente sensibles al contexto" y los "idiomas indexados" (en algún lugar entre CFL y CSL), aunque parece tener relevancia práctica para el procesamiento del lenguaje natural (pero tal vez cualquier cosa de relevancia práctica sea menos interesante en investigación teórica ;-). Además, puede mencionar GCSL ⊊ P ⊂ NP ⊂ PSPACE y CSL ⊊ PSPACE ⊊ R para mostrar la relación con las famosas clases P y NP.

Encontré en GCSL y VPL:

También estaría contento si conoces algún libro de texto más reciente sobre gramáticas formales que también se ocupen de VPL, DCLF, GCSL y gramáticas indexadas, preferiblemente con punteros a aplicaciones prácticas.

cc.complexity-theory automata-theory fl.formal-languages big-picture teaching Jakob
fuente
77
Un punto menor: no veo la ausencia de los nombres Chomsky y Schützenberger en el Complejo Zoo como una evidencia de que "la jerarquía de Chomsky está desactualizada". La jerarquía de Chomsky es una noción en la teoría del lenguaje formal. Complexity Zoo es un sitio web principalmente sobre la teoría de la complejidad, aunque contiene algunas nociones en la teoría del lenguaje formal, como los lenguajes sin contexto. Son campos relacionados pero distintos. Sería anticuado si no se mencionara en un libro de texto en la teoría del lenguaje formal, pero no sé si ese es el caso.
Tsuyoshi Ito
77
Buen punto, Tsuyoshi. Francamente, me gustaría ver un "zoológico de idiomas formales" con buena base teórica (referencias a trabajos de investigación) pero también recursos prácticos. Por ejemplo, hay docenas de variantes de sintaxis de Backus-Naur-Form y variantes de expresiones regulares (algunas de ellas incluso no son regulares). Además de la simple jerarquía de Chomsky, me resultó difícil obtener una imagen clara del estado actual de la investigación en lenguajes formales.
Jakob
También puede agregar idiomas sin estrellas estrictamente por debajo de los idiomas normales. Son como regulares, pero sin la estrella de Kleene. Bien conocido. Bien portado
wren romano
Como me mostraron varias respuestas, las gramáticas formales a la Chomsky son un método histórico para describir los lenguajes formales, que ha alcanzado sus límites. Todavía estoy buscando una buena visión general de las gramáticas formales, que no se centran en la teoría de la complejidad, ¡pero gracias por todas las referencias adicionales! Aceptaré la respuesta de mgalle porque tiene menos reputación hasta ahora.
Jakob
2
En informática, el diseño del lenguaje informático, el diseño y la programación de software, las gramáticas y los lenguajes libres de contexto y las expresiones y lenguajes regulares son equipos de trabajo básicos y tan importantes como siempre. Pero, por otro lado, para gramáticas arbitrarias, LBA y lenguajes sensibles al contexto, he visto pocas aplicaciones o ninguna.
reinierpost

Respuestas:

20

Por lo que he visto en la comunidad de procesamiento del lenguaje natural, las gramáticas formales a la Chomsky ya no se usan tanto. Ellos (también) piensan que la Jerarquía de Chomsky está desactualizada para modelar el lenguaje.

Lo que tomó su lugar es cosas como la regla de reescritura (el algoritmo de Lars), los modelos de dependencia (Dan Klein), la gramática de sustitución de árboles (el modelo DOP), las gramáticas de características binarias (Alex Clark).

mgalle
fuente
Al volver a leer mi respuesta, suena más negativo de lo que yo también quería. Nunca se suponía que RL y CFL fueran modelos realistas del lenguaje natural, y la mayoría de los "nuevos" modelos están inspirados en ellos.
mgalle
Pensé que RL ni siquiera estaba diseñado como un modelo de lenguajes naturales, sino como un modelo de algún comportamiento del sistema. [El texto original de Kleene tampoco usa la terminología del lenguaje formal.]
DG_
26

En resumen: sí.

Más particularmente: Chomsky fue uno de los primeros en formalizar una jerarquía relacionada con lenguajes, gramáticas y autómatas. Esta idea sigue siendo muy relevante y se enseña en todos los cursos de introducción a la teoría de autómatas. Sin embargo, surgió la jerarquía específica que Chomsky creó y los nombres de los elementos de la jerarquía ya no son realmente significativos. Desde entonces, hemos inventado numerosos formalismos que se encuentran entre los niveles de la jerarquía de Chomsky, por encima o por debajo. Y los nombres que usó Chomsky no son particularmente interesantes, es decir, no se basan en una medida interesante de complejidad ni nada, son solo números. ¿Deben los lenguajes ligeramente sensibles al contexto ser Tipo-1.5 o Tipo-1.7 o Tipo-1.3? A quien le importa. "Ligeramente sensible al contexto" es un nombre mucho más informativo.

Complexity Zoo es un poco diferente porque está lleno de todo tipo de equivalencias condicionales y similares. Una jerarquía más moderna para la teoría de autómatas no sería lineal (por ejemplo, comparar CFG frente a PEG), pero aún tendría una topología bien conocida. Para obtener una perspectiva sobre la teoría moderna de autómatas, debe mirar el trabajo en las bibliotecas de combinador de analizadores y algunas de las cosas sobre la unificación y la teoría de tipos (aunque ambas se extienden mucho más allá).

wren romano
fuente
44
Encontramos mejores nombres, sí. Eso no implica que los resultados estén desactualizados.
Raphael
44
@Raphael: La obsolescencia no se debe a los nombres, per se, sino a que la jerarquía específica introducida por Chomsky ya no se usa. Las inclusiones descritas por la jerarquía de Chomsky son (a) aún correctas y (b) entre las inclusiones en cualquier jerarquía moderna; pero la jerarquía de Chomsky como tal , no es terriblemente relevante, excepto que llega a alcanzar algunos de los puntos más conocidos. La gente ya no investiga sobre la jerarquía de Chomsky, sino que investiga en otros lugares. Esto no es como la torre polinómica que tiene razones para sus nombres / estructuras.
wren romano
26

Si algo en TCS está desactualizado, es esta jerarquía de inclusión del pequeño subconjunto de clases de complejidad que resultó ser conocida / considerada interesante en 1956.

Descansa en paz, Jerarquía Chomsky, y que ya no persigas el plan de estudios de teoría de pregrado.

Scott Aaronson
fuente
12
Como Juris Hartmanis una vez gritó: "¿Qué pasa con las clases de Chomsky? ¡Las clases de Chomsky son una abominación!"
Ryan Williams el
1
Ryan: ¡También recuerdo que Juris llamó al CH una "abominación"! Mientras escribía mi respuesta, estaba debatiendo si quería que su comentario se hiciera público. Pero lo conoces mejor que yo ... :-D
Scott Aaronson
Este comentario también puede estar motivado al menos un poco por la visión peyorativa de algunas ciencias de la computación teóricas y matemáticos a la lingüística y otras ciencias "débiles": xkcd.com/435 . Pero claro, la jerarquía de Chomsky hoy oscurece la visión de la teoría moderna de la complejidad, por lo que esto responde a mi pregunta. Aún así, sería bueno tener un reemplazo actualizado para comenzar con el plan de estudios de teoría de pregrado, especialmente si está más interesado en los idiomas formales y las gramáticas para aplicaciones prácticas.
Jakob
1
La Jerarquía de Chomsky enumera clases de idiomas ordenados por la complejidad de la descripción, no la complejidad de la computación que generalmente se implica cuando se usa el término "teoría de la complejidad". Están relacionados, obviamente. De todos modos, todavía no veo cómo una jerarquía (aproximada) puede ocultar clases más refinadas que difícilmente se pueden entender sin haber venido de la Jerarquía de Chomsky. Son la puerta de entrada!
Raphael
20

Si considera la Jerarquía de Chomsky con nombres "modernos" (es decir, REG, LIN, CFL, CSL, RE resp. DFA / NFA, PDA, LBA, TM), le digo: ¡No, no está desactualizado!

Motivo 0 : sigue siendo correcto en el sentido de que sus definiciones y resultados no son contradictorios con los conocimientos más recientes.

Razón 1 : Estas clases / modelos de cálculo siguen siendo los primeros que enseña, porque son simples y están bien estudiados. Intente enseñar autómata LR a un estudiante sin cubrir primero DFA / DPDA.

Razón 2 : Las clases siguen siendo los primeros / principales puntos de referencia para nuevos inventos (leí un artículo sobre múltiples CFG que, por supuesto, dijo: más que CFG, menos que CSG). Eso puede deberse en parte a que se les enseña primero, pero también a que son simples y bien estudiados.

Anti-Razón 3 : Los resultados no son obsoletos solo porque se han encontrado nuevas clases / modelos. Mantienen su valor como conceptos básicos del campo a pesar de que no se utilizan activamente en la frontera de la investigación.

Rafael
fuente
10
"Las matemáticas no se vuelven viejas , se vuelven clásicas ". (No sé a quién se atribuye esta cita, desafortunadamente).
Heinrich Apfelmus
¿No quieres decir "NPDA" en lugar de "DPDA"? Algunos lenguajes libres de contexto son reconocidos solo por autómatas no deterministas.
Zsbán Ambrus
@ ZsbánAmbrus Muy bien; Debería haber escrito solo "PDA". ¡Gracias!
Raphael
La última razón no es convincente en absoluto (supongo que es por eso que es una anti razón?). Muchos de los resultados quedan desactualizados porque están incluidos en el substrato o, a veces, incluso trivializados por un enfoque diferente del tema. No estoy diciendo que este sea el caso aquí, solo que la razón como se dijo no dice mucho. Además, una cuestión gramatical: "outdate" no es un verbo.
Sasho Nikolov
11

Creo que depende del modelo de computación. Si considera el finito / pushdown / etc. autómatas como modelo de cálculo, luego la jerarquía de Chomsky se vuelve importante (ver, por ejemplo, el libro de Sipser). Por otro lado, juega un pequeño papel en el modelo de computación de Turing.

La siguiente ilustración puede ser útil:

Editar: Los lenguajes formales juegan un papel importante en el diseño de lenguajes de computadora (como Java) y compiladores, así como en el procesamiento del lenguaje natural (PNL).

MS Dousti
fuente
Lo siento András, no puedo entender tu comentario. El OP preguntó si la jerarquía de Chomsky está desactualizada. Su razonamiento fue que no lo vio en el complejo zoológico, etc. Le respondí que si considera los autómatas como un modelo de computación, la jerarquía de Chomsky se vuelve relevante. Además, mencioné que las clases de esta jerarquía son importantes para el diseño del compilador y los algoritmos de PNL. En mi humilde opinión, eso está totalmente relacionado con la pregunta.
MS Dousti
2
Claro que la jerarquía de Chomsky no está realmente desactualizada, se encuentra en la mayoría de las introducciones de informática teórica, lenguajes formales, diseño de compiladores, etc. Pero además de esto, parece que no hay nada nuevo que contar. Creo que agradecer los idiomas entre REG y CFL, y entre CFL, también puede ser importante. ¿Es una mala idea extender la jerarquía con estos lenguajes porque la jerarquía de Chomsky huele a "obsoleto" como algo no importante para la investigación actual?
Jakob
No creo que sea una mala idea, aunque uno debe encontrar alguna aplicación para la que se ajuste la nueva extensión.
MS Dousti