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 ewe
o 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 o
de 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' |
B -> 'o'
ya no será ambigua ...S
. Mediante la aplicación de la reglaS := ...
, obtenemos...
, ..."Respuestas:
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:
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 esa
. Cada vez que este PDA comienza a tratar de procesar una cadena que comienza con una
, hay una opción. Elección significa no determinista.Considere, en cambio, la siguiente tabla de transición:
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 deq_0, (a+b)*Z0
,q1, a(a+b)*Z0
yq2, 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:
fuente
x+
- uno o másx
,(x)*
- cero o másx
?x+
típicamente se refiere a "uno o más dex
, mientras quex*
típicamente se refiere a" cero o más dex
; Puedo usarxx*
en lugar dex+
, ya que estos son idénticos.Aquí hay ejemplos (de Wikipedia):
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).
fuente
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 .
fuente
fuente
Definiciones
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
Responda a su pregunta (relación entre determinismo y ambigüedad)
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:
Un CFL aceptado por algún PDA determinista no es inherentemente ambiguo . (Existe al menos un CFG inequívoco para ello).
PD:
fuente