Estoy considerando el problema de reconocer un idioma (sobre el alfabeto 0-9 y el espacio) que contiene cadenas como "1 2 3 4 5 6" y "14 15 16 17" pero no "1 3".
Esto surgió mientras trabajaba en una tarea de análisis común donde los elementos debían estar en una lista ordenada. Me llamó la atención que si bien el análisis del resto de ese idioma era regular, esta parte era claramente irregular: puede reconocer, por ejemplo, el idioma A1A2 donde A es una cadena arbitraria 0-9. De hecho, parece ser sensible al contenido (y no libre de contexto por el lema de bombeo).
Mi primera pregunta: ¿existe una clase de lenguajes (razonablemente bien conocidos, es decir, no definidos solo para este problema) entre sensibles al contexto y libres de contexto que describa mejor su poder expresivo? He leído sobre los idiomas indexados de Aho, pero no es obvio (¡para mí!) Que estos incluso están en esa clase, por muy poderoso que sea.
Mi segunda pregunta es informal. Parece que este lenguaje es fácil de analizar y, sin embargo, es muy alto en la jerarquía. ¿Es común encontrar ejemplos similares y hay una forma estándar de tratar con ellos? ¿Existe una agrupación alternativa de clases de idiomas que sea incompatible con la inclusión de las 'habituales'?
Mi razón para pensar esto es fácil: el lenguaje se puede analizar de manera determinista, leyendo hasta llegar al final del primer número, verificando si sigue el siguiente número, y así sucesivamente. En particular, se puede analizar en O (n) tiempo con O (n) espacio; el espacio se puede reducir a sin demasiados problemas, creo. Pero es bastante difícil obtener ese tipo de rendimiento con lenguajes regulares, y mucho menos sin contexto.
fuente
Respuestas:
Parece que lo que está buscando son autómatas de múltiples cabezales (en su caso, los autómatas finitos deterministas de una cabeza y dos cabezas deberían ser suficientes). Realmente no soy un experto en esto, pero Google muestra algunas encuestas interesantes sobre esta jerarquía de idiomas, como
Marek Chrobak: Jerarquías de autómatas unidireccionales de múltiples cabezas, http://www.sciencedirect.com/science/article/pii/0304397586900939
Esto también da una respuesta a su segunda pregunta: la jerarquía de los autómatas n-head se encuentra "a través" de la jerarquía de Chomsky.
fuente