Ambigüedad en lenguajes regulares y libres de contexto.

11

Entiendo que las siguientes afirmaciones son ciertas:

  1. Dos derivaciones distintas de una cadena en un CFG dado a veces pueden atribuir el mismo árbol de análisis a la cadena.
  2. Cuando hay derivaciones de alguna cadena en un CFG dado que atribuyen diferentes árboles de análisis, el CFG es ambiguo.
  3. Algunos lenguajes libres de contexto generados por CFG ambiguos también son generados por CFG no ambiguos.
  4. Algunos lenguajes son tales que los únicos CFG que pueden generarlos (y hay algunos) son ambiguos.

Q1. Entiendo que también es indecidible si un CFG arbitrario es ambiguo, en el sentido del punto 3 anterior. ¿O es más bien indecidible si un lenguaje libre de contexto es ambiguo, en el sentido del punto 4? ¿O son ambos indecidibles?

Q2 ¿Cuál de los puntos 1-4 se vuelve falso cuando reemplazamos "sin contexto" por "regular"? ¿Las gramáticas e idiomas regulares son siempre inequívocos?

dubiousjim
fuente
Los idiomas que menciona en el punto 4 son "inherentemente ambiguos". Para Q1, creo que es indecidible si el GRAMMAR es ambiguo. Así, tanto 3 como 4 son indecidibles.
Lamine
Correcto, los idiomas del punto 4 se denominan "inherentemente ambiguos".
dubiousjim
44
Q1: ambos indecidibles. Q2: 1 no es posible, ya que a lo sumo aparece una no terminal en cualquier forma de sentencia, por lo tanto, cualquier derivación es tanto a la izquierda como a la derecha; 2 eso sigue siendo cierto; 3 sigue siendo cierto si elimina el bit `` también ''; 4 ya no es cierto, por ejemplo, al determinar su gramática, obtendrá una inequívoca.
Sylvain
1
@Sylvain, ¿eso es una respuesta?
Yuval Filmus
@Sylvain, gracias, y sí, que sea una respuesta. ¿Puedo confirmar que he entendido? re 2: ¿Entonces existe una gramática regular que puede generar la misma cadena con diferentes árboles de análisis? (Desde entonces he encontrado una referencia a "NFA ambiguos", pero no estoy seguro de que esté usando "ambig" en el sentido en que lo estoy). Re 3 y 4, creo que estás diciendo que algunos lenguajes regulares pueden ser generados por gramáticas regulares ambiguas, ¿pero también siempre serán generados por una gramática regular no ambigua?
dubiousjim

Respuestas:

19

Acerca de P1: Tanto el problema de ambigüedad (dado un CFG, si es ambiguo) como el problema de ambigüedad inherente (dado un CFG, si su lenguaje es inherentemente ambiguo, es decir, si cualquier CFG equivalente es ambiguo) son indecidibles. Aquí están las referencias originales:


Acerca de P2: Una gramática regular es una gramática libre de contexto "lineal unilateral", donde a lo sumo aparece un no terminal en cualquier parte derecha de la regla, y donde ese no terminal es el último (en las gramáticas lineales derechas ) o el primero (en izquierda gramáticas lineales ) posición. Tales gramáticas se traducen fácilmente en autómatas de estado finito equivalentes (más o menos considerando cada no terminal como un estado), que no son ambiguos si la gramática regular no es ambigua. La clase de gramáticas regulares inequívocas y autómatas inequívocos ha sido estudiada en particular por Stearns y Hunt (1985) , quienes muestran que disfrutan los algoritmos manejables para el problema de inclusión.

  1. Acerca de la relación entre derivaciones (es decir, secuencias de aplicaciones de reglas donde es una regla de la gramática) y árboles de derivación (es decir, donde un nodo etiquetado como es el padre de una secuencia de nodos , donde es una regla): en un CFG general, puede haber diferentes derivaciones, que visitan el mismo árbol de derivación de diferentes maneras.βAγβαγAαAX1,,XmAX1Xm

    Estas derivaciones diferentes ocurren porque uno tiene la opción de aplicar una regla gramatical en dos lugares diferentes en forma de oración: en una forma de oración con al menos dos no terminales y , uno puede aplicar primero y obtener , o primero y obtener , pero la aplicación de la otra regla conducirá a la misma . Imponer más a la izquierda (siempre derivando el no terminal más a la izquierda en cualquier forma de sentencia) o más a la derechaγAηBθABAαγαηBθBβγAηβθγαηβθ derivaciones impone un orden fijo para visitar los árboles de derivación, y luego hay una derivación única para un árbol de derivación dado.

    En una gramática lineal libre de contexto, no hay tal opción, ya que hay a lo sumo un no terminal en cualquier forma de oración, y hay una derivación única para un árbol de derivación dado, que es tanto a la izquierda como a la derecha.

  2. Tener dos árboles de análisis diferentes con el mismo rendimiento (secuencia de hojas) es la definición de siendo ambiguo, no cambia cuando se consideran gramáticas regulares. Alternativamente, uno también puede pedir dos derivaciones más a la izquierda diferentes. Tenga en cuenta que una derivación en una gramática unilateral corresponde a una ejecución de aceptación en su autómata de estado finito asociado, que se llama ambigua exactamente de la misma manera: cuando existen dos ejecuciones de aceptación diferentes para una entrada dada .www

  3. y 4. Si toma la vista de autómatas de estado finito, es suficiente determinar su autómata ambiguo para obtener un autómata inequívoco para el mismo idioma: habrá una sola ejecución para cualquier palabra dada. Este autómata determinista es equivalente a una gramática regular inequívoca. 

    Para responder a su comentario: existen gramáticas regulares ambiguas, por ejemplo tiene dos derivaciones más a la izquierda para : y . Una gramática equivalente no ambigua es .a S A a S B a S aSAB,Aa,BaaSAaSBaSa

Sobre la relación con Q1: es decidible si una gramática regular es ambigua (el problema de ambigüedad inherente no es muy desafiante en las gramáticas regulares, ya que la respuesta es invariablemente "no" sin siquiera mirar la gramática de entrada). Esto se puede verificar en usando una construcción cuadrada en su autómata asociado: construya el producto del autómata consigo mismo y vea si algún estado con es accesible y co-accesible. La referencia más antigua que conozco para esta idea es un artículo de Even (1965) .( q , q ) q q O(|G|2)(q,q)qq

Sylvain
fuente
1

Q1. Todo es indecidible ya que la pregunta si la gramática produce lenguaje (que contiene todas las palabras) o no es indecidible. Pero si tiene alguna gramática específica, como la gramática construida por PDA determinista, las preguntas son decidibles, pero es un caso muy aburrido.Σ GΣ

No entendí bien en qué tipo de idiomas hablas 4. Cada lenguaje CF tiene una gramática ambigua.

Q2 Todo es decidible si tienes un trato con una gramática regular. Simplemente debe construir un DFA mínimo y usarlo puede construir una gramática inequívoca. Si tiene un acuerdo con el lenguaje regular definido por la gramática CF, la respuesta es no; consulte la P1.

Alexander Rubtsov
fuente
Gracias, buena aclaración re Q2. Las preguntas sobre un idioma regular pueden ser decidibles si el idioma está especificado por una gramática regular; pero eso aún no significa que sean decidibles si el lenguaje está especificado por un CFG --- eso es lo que estás diciendo, ¿verdad? Entonces, ¿sabemos que las preguntas sobre la ambigüedad, etc., que son indecidibles para los CFG arbitrarios también son indecidibles cuando se restringen a los CFG que generan idiomas regulares?
dubiousjim
No puede ser, pero siempre son decidibles. Quiero decir, cuando tienes un trato con un lenguaje descrito por una gramática regular: la subclase de CFG, cualquier pregunta que quieras es decidible. Pero algunos CFG no regulares pueden producir un lenguaje regular, y es indecidible incluso verificar si CFG produce un lenguaje regular.
Alexander Rubtsov
2
@ alexandr-rubtsov "Cuando se trata de un lenguaje descrito por una gramática normal, cualquier pregunta que desee es decidible". Esto parece una declaración demasiado optimista ...
J.-E.
Gracias, quise decir "puede ser" en su función retórica, no en el sentido de "¿quién sabe?"
dubiousjim
@ J.-E.Pin sí, debería haber sido más delicado y decir algo como «todas las preguntas naturales como la ambigüedad».
Alexander Rubtsov
0

Depende de si sustituye 'sin contexto' por 'regular' solo delante de 'idioma (s)' o también delante de 'gramática (s)'.

Todos los lenguajes regulares son generados por gramáticas regulares , y en particular, por gramáticas regulares no ambiguas, por ejemplo, LL (1) gramáticas regulares derechas, que no son ambiguas.

reinierpost
fuente