¿En qué se diferencia la no ambigüedad del determinismo?

13

Estoy tratando de entender qué se entiende por "determinista" en expresiones como "gramática determinista sin contexto". (Hay "cosas" más deterministas en este campo). ¡Agradecería un ejemplo más que la explicación más elaborada! Si es posible.

Mi principal fuente de confusión es no poder decir cómo esta propiedad de una gramática es diferente de la (no) ambigüedad.

Lo más cerca que pude encontrar lo que significa es esta cita del documento de D. Knuth sobre la traducción de idiomas de izquierda a derecha :

Ginsburg y Greibach (1965) han definido la noción de un lenguaje determinista; mostramos en la Sección V que estos son precisamente los lenguajes para los que existe una gramática LR (k)

que se vuelve circular tan pronto como llegas al Section V, porque allí dice que lo que el analizador LR (k) puede analizar es el lenguaje determinista ...


A continuación hay un ejemplo que podría encontrar para ayudarme a entender lo que significa "ambiguo", por favor, eche un vistazo:

onewartwoearewe

Que se puede analizar como one war two ear eweo o new art woe are we, si una gramática lo permite (digamos que tiene todas las palabras que acabo de enumerar).

¿Qué debería hacer para que este lenguaje de ejemplo (no) sea determinista? (Podría, por ejemplo, eliminar la palabra ode la gramática, para que la gramática no sea ambigua).

¿Es el lenguaje anterior determinista?

PD. El ejemplo es del libro Godel, Esher, Bach: Eternal Golden Braid.


Digamos que definimos la gramática para el lenguaje de ejemplo de esta manera:

S -> A 'we' | A 'ewe'
A -> B | BA
B -> 'o' | 'new' | 'art' | 'woe' | 'are' | 'one' | 'war' | 'two' | 'ear'

Según el argumento sobre tener que analizar toda la cadena, ¿esta gramática hace que el lenguaje no sea determinista?


let explode s =
  let rec exp i l =
    if i < 0 then l else exp (i - 1) (s.[i] :: l) in
  exp (String.length s - 1) [];;

let rec woe_parser s =
  match s with
  | 'w' :: 'e' :: [] -> true
  | 'e' :: 'w' :: 'e' :: [] -> true
  | 'o' :: x -> woe_parser x
  | 'n' :: 'e' :: 'w' :: x -> woe_parser x
  | 'a' :: 'r' :: 't' :: x -> woe_parser x
  | 'w' :: 'o' :: 'e' :: x -> woe_parser x
  | 'a' :: 'r' :: 'e' :: x -> woe_parser x
  (* this line will trigger an error, because it creates 
     ambiguous grammar *)
  | 'o' :: 'n' :: 'e' :: x -> woe_parser x
  | 'w' :: 'a' :: 'r' :: x -> woe_parser x
  | 't' :: 'w' :: 'o' :: x -> woe_parser x
  | 'e' :: 'a' :: 'r' :: x -> woe_parser x
  | _ -> false;;

woe_parser (explode "onewartwoearewe");;
- : bool = true

| Label   | Pattern      |
|---------+--------------|
| rule-01 | S -> A 'we'  |
| rule-02 | S -> A 'ewe' |
| rule-03 | A -> B       |
| rule-04 | A -> BA      |
| rule-05 | B -> 'o'     |
| rule-06 | B -> 'new'   |
| rule-07 | B -> 'art'   |
| rule-08 | B -> 'woe'   |
| rule-09 | B -> 'are'   |
| rule-10 | B -> 'one'   |
| rule-11 | B -> 'war'   |
| rule-12 | B -> 'two'   |
| rule-13 | B -> 'ear'   |
#+TBLFM: @2$1..@>$1='(format "rule-%02d" (1- @#));L

Generating =onewartwoearewe=

First way to generate:

| Input             | Rule    | Product           |
|-------------------+---------+-------------------|
| ''                | rule-01 | A'we'             |
| A'we'             | rule-04 | BA'we'            |
| BA'we'            | rule-05 | 'o'A'we'          |
| 'o'A'we'          | rule-04 | 'o'BA'we'         |
| 'o'BA'we'         | rule-06 | 'onew'A'we'       |
| 'onew'A'we'       | rule-04 | 'onew'BA'we'      |
| 'onew'BA'we'      | rule-07 | 'onewart'A'we'    |
| 'onewart'A'we'    | rule-04 | 'onewart'BA'we'   |
| 'onewart'BA'we'   | rule-08 | 'onewartwoe'A'we' |
| 'onewartwoe'A'we' | rule-03 | 'onewartwoe'B'we' |
| 'onewartwoe'B'we' | rule-09 | 'onewartwoearewe' |
|-------------------+---------+-------------------|
|                   |         | 'onewartwoearewe' |

Second way to generate:

| Input             | Rule    | Product           |
|-------------------+---------+-------------------|
| ''                | rule-02 | A'ewe'            |
| A'ewe'            | rule-04 | BA'ewe'           |
| BA'ewe'           | rule-10 | 'one'A'ewe'       |
| 'one'A'ewe'       | rule-04 | 'one'BA'ewe'      |
| 'one'BA'ewe'      | rule-11 | 'onewar'A'ewe'    |
| 'onewar'A'ewe'    | rule-04 | 'onewar'BA'ewe'   |
| 'onewar'BA'ewe'   | rule-12 | 'onewartwo'A'ewe' |
| 'onewartwo'A'ewe' | rule-03 | 'onewartwo'B'ewe' |
| 'onewartwo'B'ewe' | rule-13 | 'onewartwoearewe' |
|-------------------+---------+-------------------|
|                   |         | 'onewartwoearewe' |
wvxvw
fuente
1
-1, ya que la pregunta ahora tiene poco sentido. En primer lugar, una cadena no es un idioma; las cadenas no son ambiguas, inequívocas, deterministas o no deterministas; Son solo cuerdas. La gramática que da no genera la cadena de ejemplo. No he verificado las 180 derivaciones para ver si hay duplicados, pero en teoría eso es todo lo que necesitarías hacer para ver si la gramática es ambigua. Lamentablemente, el lenguaje no puede ser inherentemente ambiguo, ya que el lenguaje es finito, por lo tanto regular, por lo tanto aceptado por un DPDA, por lo tanto, determinista.
Patrick87
@ Patrick87 eh? ¿Dónde dice que la cadena es el idioma? Esta cadena es un producto de ejemplo, y seguro que es posible generarla usando la gramática dada. ¿Qué te hace pensar lo contrario? La cadena en cuestión es exactamente el caso, donde dos secuencias diferentes de aplicaciones de reglas producen la misma cadena, por lo tanto, la gramática es ambigua, pero si elimina algunas reglas (por ejemplo, B -> 'o'ya no será ambigua ...
wvxvw
En primer lugar, ¿puede proporcionar una derivación de la cadena de ejemplo utilizando la gramática? De su propia pregunta: "¿Es el lenguaje anterior determinista?" Nunca nombras un idioma, solo una cadena, generada por una infinidad de gramáticas, aunque no sea la que propones.
Patrick87
¿Puedes escribirlo en inglés? Por ejemplo, "Comience con S. Mediante la aplicación de la regla S := ..., obtenemos ..., ..."
Patrick87
@ Patrick87 Agregué el procedimiento de generación paso a paso y me di cuenta de que cometí un error en la gramática, lo que solucioné.
wvxvw

Respuestas:

9

Un PDA es determinista, por lo tanto, un DPDA, si para cada configuración accesible del autómata, hay como máximo una transición (es decir, como máximo una nueva configuración posible). Si tiene un PDA que puede alcanzar alguna configuración para la que pueden ser posibles dos o más transiciones únicas, no tiene un DPDA.

Ejemplo:

Q={q0 0,q1}Σ=Γ={un,si}UN=q0 0δ

q    e    s    q'   s'
--   --   --   --   --
q0   a    Z0   q1   aZ0
q0   a    Z0   q2   bZ0
...

Estos son PDA no deterministas porque la configuración inicial - q_0, Z0- es accesible, y hay dos transiciones válidas que se alejan si el símbolo de entrada lo es a. Cada vez que este PDA comienza a tratar de procesar una cadena que comienza con un a, hay una opción. Elección significa no determinista.

Considere, en cambio, la siguiente tabla de transición:

q    e    s    q'   s'
--   --   --   --   --
q0   a    Z0   q1   aZ0
q0   a    Z0   q2   bZ0
q1   a    a    q0   aa
q1   a    b    q0   ab
q1   a    b    q2   aa
q2   b    a    q0   ba
q2   b    b    q0   bb
q2   b    a    q1   bb

Puede sentirse tentado a decir que este PDA no es determinista; después de todo, hay dos transiciones válidas fuera de la configuración q1, b(a+b)*, por ejemplo. Sin embargo, dado que esta configuración no es accesible por ninguna ruta a través del autómata, no cuenta. Las configuraciones sólo accesible son un subconjunto de q_0, (a+b)*Z0, q1, a(a+b)*Z0y q2, b(a+b)*Z0, y para cada una de estas configuraciones, se define como máximo una transición.

Una CFL es determinista si es el lenguaje de alguna DPDA.

Un CFG no es ambiguo si cada cadena tiene como máximo una derivación válida de acuerdo con el CFG. De lo contrario, la gramática es ambigua. Si tiene un CFG y puede producir dos árboles de derivación diferentes para alguna cadena, tiene una gramática ambigua.

Una CFL es intrínsecamente ambigua si no es el lenguaje de una CFG inequívoca.

Tenga en cuenta lo siguiente:

  • Una CFL determinista debe ser el lenguaje de algunos DPDA.
  • Cada CFL es el lenguaje de infinitos PDA no deterministas.
  • Un CFL inherentemente ambiguo no es el lenguaje de ningún CFG inequívoco.
  • Cada CFL es el lenguaje de infinitos CFG ambiguos.
  • Un CFL inherentemente ambiguo no puede ser determinista.
  • Un CFL no determinista puede o no ser inherentemente ambiguo.
Patrick87
fuente
1
Wiki dice que PDA no es determinista (puede haber una versión determinista y una no determinista), pero también podría omitir la primera parte de la oración, realmente no está contribuyendo a lo que está diciendo: / Pero, nuevamente, esto define un lenguaje determinista como lenguaje de entrada de algo determinista, y ese algo se llama determinista porque acepta lenguaje determinista, es como decir "la hierba es verde porque el verde es el color de la hierba". Es cierto, pero no es útil :( ¡Por favor, el ejemplo sería más que precioso!
wvxvw
@wvxvw: no estás leyendo esto correctamente. Dice: "Un PDA es determinista si y solo si cada estado / símbolo / triple de stacktop tiene solo un estado siguiente". No hay nada en esa definición sobre qué idioma acepta el autómata.
Wandering Logic
2
@wvxvw La definición de PDA determinista, o DPDA, que doy de ninguna manera o forma, se basa en la definición de un lenguaje determinista libre de contexto. Defino DPDA basados ​​solo en las propiedades del autómata. Luego defino qué es un CFL determinista en términos de la definición de un DPDA. Vuelva a leer la respuesta a la luz de estos y los comentarios de Wandering Logic e intente ver si esto tiene sentido. Me esforzaré por proporcionar algunos breves ejemplos.
Patrick87
q1,b(a+b)q2,b(a+b)Q={q0,...q2}el personaje actual? Además, ¿es correcta mi interpretación? x+- uno o más x, (x)*- cero o más x?
wvxvw
@wvxvw La configuración se refiere al estado actual y al contenido actual de la pila. x+típicamente se refiere a "uno o más de x, mientras que x*típicamente se refiere a" cero o más de x; Puedo usar xx*en lugar de x+, ya que estos son idénticos.
Patrick87
7

Aquí hay ejemplos (de Wikipedia):

S0S0|1S1|ε

Un lenguaje libre de contexto es determinista si y solo si existe al menos un autómata determinista que acepta ese lenguaje. (También puede haber muchos autómatas pushdown no deterministas que aceptan el lenguaje, y aún así sería un lenguaje determinista). Esencialmente, un autómata pushdown determinista es aquel en el que las transiciones de la máquina se basan determinísticamente en el estado actual, el símbolo de entrada y el símbolo actual más alto de la pila . Deterministaaquí significa que no hay más de una transición de estado para cualquier estado / símbolo de entrada / símbolo de pila superior. Si tiene dos o más estados siguientes para algún estado / símbolo de entrada / triple símbolo de pila superior, entonces el autómata no es determinista. (Debería "adivinar" qué transición tomar para decidir si el autómata acepta o no).

Lo que Knuth demostró fue que cada gramática LR (k) tiene un autómata determinista pushdown y que cada autómata determinista pushdown tiene una gramática LR (k). Por lo tanto, las gramáticas LR (k) y los autómatas deterministas pushdown pueden manejar el mismo conjunto de lenguajes. Pero el conjunto de lenguajes que tienen un autómata determinista que los acepta es (por definición) los lenguajes deterministas. El argumento no es circular.

Entonces, el lenguaje determinista implica que existe una gramática inequívoca. Y hemos mostrado una gramática inequívoca que no tiene un autómata de empuje determinista (y, por lo tanto, es una gramática inequívoca que acepta un lenguaje no determinista).

{anbmcmdn|n,m>0}{anbncmdm|n,m>0}{anbnccdn|n>0}

Lógica Errante
fuente
¿Puede explicarnos por qué tener que mirar la cadena completa antes de determinar el medio hace que este lenguaje no sea determinista? Leí otra explicación de lo que es "determinista", y allí dice que "si no necesita dar marcha atrás al analizar, ese lenguaje es determinista". No veo la necesidad de retroceder para analizar este idioma ...
wvxvw
1
Considere la cadena de entrada "10011001". El autómata pushdown no sabe cuánto dura la cadena hasta que llega al final. Cuando llegue al segundo 0, debe elegir: ¿es esta la cadena de 4 caracteres "1001" o una cadena más larga que se parece a "100 ???? 001"? Cuando llegue al quinto carácter que aún no conoce: ¿es esta la cadena de 8 caracteres "10011001" o una cadena más larga que se parece a "10011 ???? 11001"?
Wandering Logic
1
Lo de "analizar toda la cadena" no es la definición de no determinista. Solo intentaba agregar algo de intuición. Tanto @ Patrick87 como yo les dimos la definición real de determinista: de cada estado hay como máximo un estado siguiente. Si un idioma no tiene una gramática inequívoca, debe ser no determinista. No puedo responder sobre su ejemplo sin hacer más trabajo: ha mostrado una gramática ambigua, pero eso no es lo que importa, debe demostrar que no hay una gramática inequívoca si quiere demostrar que el lenguaje es inherentemente ambiguo.
Wandering Logic
1
@wvxvw Si está buscando un procedimiento computacional, es probable que no tenga suerte ... según en.wikipedia.org/wiki/List_of_undecidable_problems , es indecidible si un CFG es ambiguo, y mucho menos si su lenguaje es inherentemente ambiguo ; También es indecidible si un CFG genera todas las cadenas. Dado esto, dudo seriamente que sea decidible, mucho menos eficiente decidir, si el lenguaje de un CFG es un CFL determinista.
Patrick87
1
@wvxvw Si eres tan afortunado como eso, estás lidiando con lo que llamamos un caso feliz, es decir, no uno de los casos que hace que este sea un problema indecidible. Puede definir heurísticas que funcionen para muchos casos felices y no exploten en el resto, pero no funcionarán en todos los casos felices; si lo hicieran, tendría un factor decisivo para el problema, que según nuestra premisa es imposible.
Patrick87
5

Los lenguajes deterministas sin contexto son aquellos que son aceptados por algún autómata determinista (los lenguajes sin contexto son aquellos aceptados por algún autómata no determinista). Como tal, es una propiedad de un lenguaje más que de una gramática . En contraste, la ambigüedad es una propiedad de una gramática, mientras que la ambigüedad inherente es una propiedad de un lenguaje (un lenguaje sin contexto es intrínsecamente ambiguo si toda gramática sin contexto para el lenguaje es ambigua).

Hay una conexión entre las dos definiciones: los lenguajes deterministas libres de contexto nunca son inherentemente ambiguos, como se muestra en la respuesta a esta pregunta .

Yuval Filmus
fuente
Lo siento, eso no es muy útil. De hecho, comencé con DPDA, pero nunca explica por qué se llama determinista. Esta es una definición que es fácil de encontrar en Wikipedia / Google para otros documentos. Pero, ¿qué propiedad de la gramática / lenguaje / analizador describe la palabra "determinista"? En otras palabras, ¿qué debería suceder en la gramática para que pueda llamarse determinista?
wvxvw
Lo siento, si comento demasiado. La confusión se debe a que no puedo decir, por ejemplo, al mirar un lenguaje si es determinista o no, y no sabría por dónde comenzar a identificar el "determinismo" del lenguaje. Un ejemplo de un lenguaje que es determinista y luego cambia de la manera que lo hace no determinista sería inmensamente útil.
wvxvw
1
LR(k)
1
Lo siento, aún no es útil. Entiendo lo que estás diciendo, pero no me ayuda a reconocer un lenguaje que es determinista y distinguirlo de no determinista. Para darle un ejemplo: si un idioma tiene una regla de producción que crea un problema de paréntesis equilibrado, inmediatamente sé que FSM no puede analizarlo. (Porque requeriría una pila). Pero cuando solo mencionas otro formalismo, solo se vuelve recursivo, no me está ayudando a entender cómo ese lenguaje debería diferir de otro.
wvxvw
En otras palabras (como mencionó en un comentario anterior), desea ejemplos de lenguajes deterministas y no deterministas sin contexto del mismo "tipo". Tal vez deberías hacer una pregunta enfocada sobre eso.
Yuval Filmus
1

{a,b}{w(a+b)w=wR}SaSa|bSb|a|b|ϵasiunsiunsi

PMar
fuente
1

Definiciones

  1. Un aceptador de pushdown determinista (DPDA) es un autómata de pushdown que nunca tiene una opción en su movimiento.
  2. DPDA y NPDA no son equivalentes.
  3. Un CFG no es determinista si hay al menos dos producciones con el mismo prefijo terminal en el lado derecho de ellas.
  4. Un CFG es ambiguo si existe algún w ∈ L (G) que tiene al menos dos árboles de derivación distintos. Por lo tanto, tiene dos o más derivaciones más a la izquierda o más a la derecha que corresponden a dos árboles de derivación diferentes.
  5. Un CFG no es ambiguo si cada cadena tiene como máximo una derivación válida de acuerdo con el CFG. De lo contrario, la gramática es ambigua.
  6. Una CFL es intrínsecamente ambigua si no es el lenguaje de una CFG inequívoca. No puede tener ningún DPDA.
    Si cada gramática que genera CFL es ambigua, entonces la CFL se llama inherentemente ambigua . Por lo tanto, no es el lenguaje de ningún CFG inequívoco.

Hechos

  1. Cada CFL es el lenguaje de infinitos PDA no deterministas.
  2. Cada CFL es el lenguaje de infinitos CFG ambiguos.
  3. Una CFL aceptada por algunos DPDA no es inherentemente ambigua. (Existe al menos un CFG inequívoco para ello).
  4. Un CFL aceptado por NDPDA puede o no ser inherentemente ambiguo, ya que puede existir algún DPDA (o CFG no ambiguo) para él.
  5. Un CFL generado por CFG ambiguo puede o no ser inherentemente ambiguo, ya que puede existir un CFG no ambiguo (o DPDA) para él.
  6. Un CFL generado por al menos un CFG no ambiguo no es inherentemente ambiguo. (Existen algunos DPDA para ello).
  7. Una gramática no determinista puede o no ser ambigua.

Responda a su pregunta (relación entre determinismo y ambigüedad)

  1. La (no) ambigüedad se aplica principalmente a las gramáticas (aquí CFG). El (no) determinismo se aplica tanto a las gramáticas como al autómata (aquí PDA).

    Si desea diferencias lógicas, puede ver los últimos cuatro puntos en la sección de hechos, ya que tratan de relacionar ambigüedad y determinismo. Aquí los estoy repitiendo nuevamente:

  2. Un CFL aceptado por algún PDA determinista no es inherentemente ambiguo . (Existe al menos un CFG inequívoco para ello).

  3. Un CFL aceptado por PDA no determinista puede o no ser inherentemente ambiguo, ya que puede existir algún DPDA (o CFG no ambiguo ) para él.
  4. Un CFL generado por CFG ambiguo puede o no ser inherentemente ambiguo, ya que puede existir un CFG no ambiguo (o PDA determinista ) para él.
  5. A CFL generada por al menos una inequívoca CFG no es inherentemente ambiguo . (Existen algunos DPDA para ello).
  6. Una gramática no determinista puede o no ser ambigua .

PD:

  1. La respuesta aceptada utiliza líneas como "CFL es determinista", "CFL determinista", "CFL no puede ser determinista", "Una CFL no determinista". Supongo que los adjetivos "determinista" y "ambiguo" no se aplican a CFL, sino a PDA y CFG (aunque el adjetivo "intrínsecamente ambiguo" se aplica a CFL) Aunque no quiero criticar la respuesta original, como yo mismo aprendí crucial puntos de ella. (De hecho, literalmente he copiado y pegado algunas líneas de esa respuesta). Pero aún así sentí que debería hacerse más correcto. Así que traté de poner las cosas más claramente aquí en dos partes, definiciones y hechos (podría haberlo hecho innecesariamente detallado y largo). Supongo que debería haber editado la respuesta original, pero luego implicará eliminar muchos puntos que usan las líneas anteriores. Y no sé si esto hará que sea una edición válida, ya que implica una reescritura completa.
  2. Tenga en cuenta que he puesto palabras cuantitativas en negrita y cursiva para resaltar las diferencias comparativas en diferentes definiciones y hechos. Los términos de definición solo están en negrita .
  3. Algunos de los puntos que he hecho yo mismo, por lo que necesitaré la confirmación de alguien bien informado aquí sobre la corrección de cada punto.
Maha
fuente
PS 1 está mal: hay una definición estándar para CFL deterministas / ambiguas, a saber, se definen como aquellas para las cuales todos los CFG son deterministas / ambiguos.
reinierpost
acabo de darme cuenta de que el hecho 7 está mal. También el punto 6 de la segunda última lista es igual y está mal.
Maha
De hecho ... el determinismo no tiene ambigüedad en ningún momento durante el análisis, por lo que es estrictamente más fuerte que la ambigüedad (es decir, ambigüedad incluso después de que se haya completado el análisis).
reinierpost