En quoi la non-ambuiguïté est-elle différente du déterminisme?

13

J'essaie de comprendre ce que l'on entend par «déterministe» dans des expressions telles que «grammaire déterministe sans contexte». (Il y a des "choses" plus déterministes dans ce domaine). J'apprécierais un exemple plus que l'explication la plus élaborée! Si possible.

Ma principale source de confusion est de ne pas pouvoir dire en quoi cette propriété d'une grammaire est différente de (non) l'ambiguïté.

Le plus proche que j'ai pu trouver ce que cela signifie est cette citation de l'article de D. Knuth sur la traduction des langues de gauche à droite :

Ginsburg et Greibach (1965) ont défini la notion de langage déterministe; nous montrons dans la section V que ce sont précisément les langues pour lesquelles il existe une grammaire LR (k)

qui devient circulaire dès que vous arrivez à la Section V, car là, il est dit que ce que l'analyseur LR (k) peut analyser est le langage déterministe ...


Vous trouverez ci-dessous un exemple que je pourrais trouver pour m'aider à comprendre ce que signifie «ambigu», veuillez jeter un œil:

onewartwoearewe

Qui peut être analysé comme one war two ear eweou o new art woe are we- si une grammaire le permet (disons qu'elle contient tous les mots que je viens d'énumérer).

Que devrais-je faire pour rendre cet exemple de langage (non) déterministe? (Je pourrais, par exemple, supprimer le mot ode la grammaire, pour que la grammaire ne soit pas ambiguë).

Le langage ci-dessus est-il déterministe?

PS. L'exemple est tiré du livre Godel, Esher, Bach: Eternal Golden Braid.


Disons que nous définissons la grammaire de l'exemple de langue comme suit:

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

Par l'argument d'avoir à analyser la chaîne entière, cette grammaire rend-elle le langage non déterministe?


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
la source
1
-1, car la question n'a plus guère de sens. Tout d'abord, une chaîne n'est pas une langue; les chaînes ne sont pas ambiguës, non ambiguës, déterministes ou non déterministes; ce ne sont que des cordes. La grammaire que vous donnez ne génère pas la chaîne d'exemple. Je n'ai pas vérifié les 180 dérivations pour voir s'il y a des doublons, mais en théorie c'est tout ce que vous devez faire pour voir si la grammaire est ambiguë. Malheureusement, la langue ne peut pas être intrinsèquement ambiguë, car la langue est finie, donc régulière, donc acceptée par un DPDA, donc déterministe.
Patrick87
@ Patrick87 hein? Où est-il dit que la chaîne est la langue? Cette chaîne est un exemple de produit, et bien sûr, il est possible de générer en utilisant la grammaire donnée. Qu'est-ce qui vous fait penser le contraire? La chaîne en question est exactement le cas, où deux séquences différentes d'applications de règles produisent la même chaîne, donc la grammaire est ambiguë, mais si vous supprimez certaines règles (par exemple B -> 'o', alors ce ne sera plus ambigu ...
wvxvw
Tout d'abord, pouvez-vous fournir une dérivation de la chaîne d'exemple en utilisant la grammaire? D'après votre propre question: "Le langage ci-dessus est-il déterministe?" Vous ne nommez jamais une langue, juste une chaîne, générée par une infinité de grammaires, mais pas celle que vous proposez.
Patrick87
Pouvez-vous l'écrire en anglais? Par exemple, "Commencez par S. Par l'application de la règle S := ..., nous obtenons ..., ..."
Patrick87
@ Patrick87 J'ai ajouté une procédure de génération étape par étape, et j'ai réalisé que j'avais fait une erreur de grammaire, que j'ai corrigée.
wvxvw

Réponses:

9

Un PDA est déterministe, donc un DPDA, si pour chaque configuration accessible de l'automate, il y a au plus une transition (c'est-à-dire au plus une nouvelle configuration possible). Si vous avez un PDA qui peut atteindre une configuration pour laquelle deux ou plusieurs transitions uniques peuvent être possibles, vous n'avez pas de DPDA.

Exemple:

Q={q0,q1}Σ=Γ={a,b}A=q0δ

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

Ce sont des PDA non déterministes car la configuration initiale - q_0, Z0- est accessible, et il y a deux transitions valides qui s'éloignent si le symbole d'entrée est a. Chaque fois que ce PDA commence à essayer de traiter une chaîne qui commence par un a, il y a un choix. Le choix signifie non déterministe.

Considérez plutôt la table de transition suivante:

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

Vous pourriez être tenté de dire que ce PDA n'est pas déterministe; après tout, il y a deux transitions valides en dehors de la configuration q1, b(a+b)*, par exemple. Cependant, comme cette configuration n'est accessible par aucun chemin à travers l'automate, elle ne compte pas. Les configurations sont accessibles seulement un sous - ensemble q_0, (a+b)*Z0, q1, a(a+b)*Z0et q2, b(a+b)*Z0, ainsi que pour chacune de ces configurations, tout au plus une transition est définie.

Une LFC est déterministe si elle est la langue de certains DPDA.

Un CFG est sans ambiguïté si chaque chaîne a au plus une dérivation valide selon le CFG. Sinon, la grammaire est ambiguë. Si vous avez un CFG et que vous pouvez produire deux arbres de dérivation différents pour une chaîne, vous avez une grammaire ambiguë.

Un CFL est intrinsèquement ambigu si ce n'est le langage d'aucun CFG sans ambiguïté.

Notez les points suivants:

  • Une LFC déterministe doit être le langage de certains DPDA.
  • Chaque LFC est le langage d'une infinité de PDA non déterministes.
  • Un CFL intrinsèquement ambigu n'est pas le langage d'un CFG sans ambiguïté.
  • Chaque CFL est la langue d'une infinité de CFG ambigus.
  • Une LFC intrinsèquement ambiguë ne peut pas être déterministe.
  • Une LFC non déterministe peut ou peut ne pas être intrinsèquement ambiguë.
Patrick87
la source
1
Le Wiki dit que le PDA n'est pas déterministe (il peut y avoir une version déterministe et une non déterministe), mais vous pourriez aussi bien omettre la première partie de la phrase, cela ne contribue pas vraiment à ce que vous dites: / Mais, encore une fois, cela définit un langage déterministe comme langue d'entrée de quelque chose déterministe, et ce quelque chose est appelé déterministe parce qu'il accepte un langage déterministe - c'est comme dire "l'herbe est verte parce que le vert est la couleur de l'herbe". C'est vrai, mais pas utile :( S'il vous plaît, l'exemple serait plus que précieux!
wvxvw
@wvxvw: vous ne lisez pas cela correctement. Il dit: "Un PDA est déterministe si et seulement si chaque triple état / symbole / stacktop n'a qu'un seul état suivant." Il n'y a rien dans cette définition sur la langue acceptée par l'automate.
Wandering Logic
2
@wvxvw La définition de PDA déterministe, ou DPDA, que je ne donne en aucune façon, forme ou forme repose sur la définition d'un langage sans contexte déterministe. Je définis les DPDA basés uniquement sur les propriétés de l'automate. Je définis ensuite ce qu'est une LFC déterministe en termes de définition d'un DPDA. Veuillez relire la réponse à la lumière de ceux-ci et des commentaires de Wandering Logic et essayez de voir si cela a du sens. Je m'efforcerai de fournir quelques brefs exemples.
Patrick87
q1,b(a+b)q2,b(a+b)Q={q0,...q2}le personnage actuel? Aussi, mon interprétation est-elle correcte? x+- un ou plusieurs x, (x)*- zéro ou plus x?
wvxvw
La configuration @wvxvw fait référence à l'état actuel et au contenu actuel de la pile. x+se réfère généralement à "un ou plusieurs de x, tandis que x*se réfère généralement à" zéro ou plusieurs de x; Je peux utiliser xx*à la place de x+, car ils sont identiques.
Patrick87
7

Voici des exemples (de Wikipedia):

S0S0|1S1|ε . Le langage n'est pas déterministe car vous devez regarder toute la chaîne pour savoir où se trouve le milieu. La grammaire est sans ambiguïté car il existe un et un seul arbre d'analyse pour chaque chaîne de la langue.

Un langage sans contexte est déterministe si et seulement s'il existe au moins un automate déterministe déroulant qui accepte ce langage. (Il peut également y avoir beaucoup d'automates push-down non déterministes qui acceptent le langage, et ce serait toujours un langage déterministe.) Essentiellement, un automate push-down déterministe est celui où les transitions machine sont déterminées de manière déterministe en fonction de l'état actuel, le symbole d'entrée et le symbole le plus haut actuel de la pile . Déterministeici signifie qu'il n'y a pas plus d'une transition d'état pour un état / symbole d'entrée / symbole de pile supérieur. Si vous avez deux ou plusieurs états suivants pour un triple état / symbole d'entrée / symbole de pile supérieur, l'automate n'est pas déterministe. (Vous devez "deviner" la transition à effectuer pour décider si l'automate accepte ou non.)

Ce que Knuth a prouvé, c'est que chaque grammaire LR (k) a un automate déterministe de refoulement et que chaque automate déterministe pushdown a une grammaire LR (k). Ainsi, les grammaires LR (k) et les automates déterministes de refoulement peuvent gérer le même ensemble de langues. Mais l'ensemble des langages qui ont un automate de refoulement déterministe qui les accepte est (par définition) les langages déterministes. L'argument n'est pas circulaire.

Le langage déterministe implique donc qu'il existe une grammaire sans ambiguïté. Et nous avons montré une grammaire non ambiguë qui n'a pas d'automate pushdown déterministe (et donc c'est une grammaire non ambiguë qui accepte un langage non déterministe.)

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

Logique errante
la source
Pouvez-vous expliquer, pourquoi avoir à regarder toute la chaîne avant de déterminer le milieu rend ce langage non déterministe? J'ai lu une autre explication de ce qu'est "déterministe", et là, il est dit que "si vous n'avez pas besoin de revenir en arrière lors de l'analyse, ce langage est déterministe". Je ne vois pas la nécessité de revenir en arrière pour analyser cette langue ...
wvxvw
1
Considérez la chaîne d'entrée "10011001". Les automates pushdown ne savent pas combien de temps la chaîne est jusqu'à ce qu'elle arrive à la fin. Lorsque vous arrivez au deuxième 0, vous devez faire un choix: s'agit-il de la chaîne de 4 caractères "1001", ou d'une chaîne plus longue qui ressemble à "100 ???? 001"? Lorsque vous arrivez au cinquième caractère, vous ne savez toujours pas: s'agit-il de la chaîne de 8 caractères "10011001" ou d'une chaîne plus longue qui ressemble à "10011 ???? 11001"?
Wandering Logic
1
La chose "analyser la chaîne entière" n'est pas la définition de non déterministe. C'était juste une intuition que j'essayais d'ajouter. @ Patrick87 et moi vous avons donné la vraie définition de déterministe: de chaque état il y a au plus un état suivant. Si une langue n'a pas de grammaire non ambiguë, elle doit être non déterministe. Je ne peux pas répondre à votre exemple sans faire plus de travail: vous avez montré une grammaire ambiguë, mais ce n'est pas ce qui compte, vous devez démontrer qu'il n'y a pas de grammaire non ambiguë si vous voulez montrer que la langue est intrinsèquement ambiguë.
Wandering Logic
1
@wvxvw Si vous recherchez une procédure de calcul, vous n'avez probablement pas de chance ... selon en.wikipedia.org/wiki/List_of_undecidable_problems , il est indécidable qu'un CFG soit ambigu, et encore moins si son langage est intrinsèquement ambigu. ; il est également indécidable qu'un CFG génère toutes les chaînes. Compte tenu de cela, je doute sérieusement qu'il soit décidable, beaucoup moins efficace de décider, si le langage d'un CFG est un CFL déterministe.
Patrick87
1
@wvxvw S'il vous arrive d'être aussi chanceux que cela, vous avez affaire à ce que nous appelons un cas heureux, c'est-à-dire pas un des cas qui en fait un problème indécidable. Vous pouvez définir des heuristiques qui fonctionnent pour de nombreux cas heureux et ne pas exploser sur le reste, mais elles ne fonctionneront pas sur tous les cas heureux; S'ils le faisaient, vous auriez un décideur pour le problème, ce qui, selon nous, est impossible.
Patrick87
5

Les langages libres de contexte déterministes sont ceux qui sont acceptés par un automate de refoulement déterministe (les langages sans contexte sont ceux acceptés par certains automate de refoulement non déterministe). En tant que tel, c'est une propriété d'une langue plutôt que d'une grammaire . En revanche, l' ambiguïté est une propriété d'une grammaire, tandis que l'ambiguïté inhérente est une propriété d'une langue (une langue sans contexte est intrinsèquement ambiguë si chaque grammaire sans contexte de la langue est ambiguë).

Il existe un lien entre les deux définitions: les langages déterministes sans contexte ne sont jamais intrinsèquement ambigus, comme le montre la réponse à cette question .

Yuval Filmus
la source
Désolé, ce n'est pas très utile. En fait, j'ai commencé avec DPDA, mais cela n'explique jamais pourquoi on l'appelle déterministe. Il s'agit d'une définition facile à trouver sur Wikipedia / Google pour d'autres articles. Mais quelle propriété de la grammaire / langue / analyseur est décrite par le mot "déterministe"? En d'autres termes, que doit-il se passer dans la grammaire pour qu'elle soit qualifiée de déterministe?
wvxvw
Désolé, si je commente trop. La confusion vient du fait que je ne peux pas dire, par exemple, en regardant un langage s'il est déterministe ou non, et je ne saurais pas par où commencer pour identifier le «déterminisme» du langage. Un exemple de langage déterministe, puis modifié de manière à le rendre non déterministe, serait extrêmement utile.
wvxvw
1
LR(k)
1
Désolé, toujours pas utile. Je comprends ce que vous dites, mais cela ne m'aide pas à reconnaître un langage qui est déterministe et à le distinguer du non-déterministe. Pour vous donner un exemple: si une langue a une règle de production qui crée un problème de parenthèse équilibrée, je sais immédiatement qu'elle ne peut pas être analysée par FSM. (Parce qu'il faudrait une pile). Mais quand vous venez de mentionner un autre formalisme, cela ne devient récursif, cela ne m'aide pas à comprendre en quoi ce langage devrait différer d'un autre.
wvxvw
En d'autres termes (comme vous l'avez mentionné dans un commentaire précédent), vous voulez des exemples de langages sans contexte déterministes et non déterministes du même "tri". Vous devriez peut-être poser une question précise à ce sujet.
Yuval Filmus
1

Peut-être qu'un exemple aiderait ici. Considérez le langage des cordes palindromiques sur{une,b}, c'est à dire: {w(une+b)w=wR}. Ceci est généré par la grammaireSuneSune|bSb|une|b|ϵ. Il s'agit d'une grammaire sans ambiguïté pour une langue sans ambiguïté. Un PDA acceptant cette langue pousserait simplementune'le sable best jusqu'à ce qu'il localise le milieu de la chaîne, peut-être en manger un une ou b (pour les chaînes de longueur impaire), puis correspondant une'le sable b's en lisant l'entrée et en faisant sauter la pile jusqu'à ce que les deux soient vides. Mais il n'y a aucun moyen de créer un PDA DETERMINISTIQUE pour cette langue, car il n'y a aucun moyen pour le PDA de localiser le centre de la chaîne sans deviner.

PMar
la source
1

Définitions

  1. Un accepteur pushdown déterministe (DPDA) est un automate pushdown qui n'a jamais le choix dans son mouvement.
  2. DPDA et NPDA ne sont pas équivalents.
  3. Un CFG n'est pas déterministe s'il y a au moins deux productions avec le même préfixe de terminal sur le côté droit.
  4. Un CFG est ambigu si il existe un w ∈ L (G) qui a au moins deux arbres de dérivation distincts. Ainsi, il a deux ou plusieurs dérivations à l'extrême gauche ou à l'extrême droite correspondant à deux arbres de dérivation différents.
  5. Un CFG est sans ambiguïté si chaque chaîne a au plus une dérivation valide selon le CFG. Sinon, la grammaire est ambiguë.
  6. Un CFL est intrinsèquement ambigu si ce n'est le langage d' aucun CFG sans ambiguïté. Il ne peut pas avoir de DPDA.
    Si chaque grammaire qui génère CFL est ambiguë, alors la CFL est appelée intrinsèquement ambiguë . Il est donc pas la langue de toute GFR sans ambiguïté.

Les faits

  1. Chaque LFC est le langage d'une infinité de PDA non déterministes.
  2. Chaque CFL est le langage d'une infinité de CFG ambigus.
  3. Une LFC acceptée par certains DPDA n'est pas intrinsèquement ambiguë. (Il existe au moins un CFG sans ambiguïté pour cela.)
  4. Une LFC acceptée par le NDPDA peut être ambiguë ou non, car il peut exister certains DPDA (ou un CFG non ambigu) pour elle.
  5. Un CFL généré par un CFG ambigu peut ou peut ne pas être intrinsèquement ambigu car il peut exister un CFG sans ambiguïté (ou DPDA).
  6. Un CFL généré par au moins un CFG non ambigu n'est pas intrinsèquement ambigu. (Il existe des DPDA pour cela.)
  7. Une grammaire non déterministe peut être ambiguë ou non.

Réponse à votre question (relation entre déterminisme et ambiguïté)

  1. La (non) ambiguïté s'applique principalement aux grammaires (ici les CFG). Le (non) déterminisme s'applique à la fois aux grammaires et aux automates (ici les PDA).

    Si vous voulez des différences logiques, vous pouvez regarder les quatre derniers points dans la section des faits car ils essaient de relier à la fois l'ambiguïté et le déterminisme. Ici, je les répète à nouveau:

  2. Une LFC acceptée par certains PDA déterministes n'est pas intrinsèquement ambiguë . (Il existe au moins un CFG sans ambiguïté pour cela.)

  3. Une LFC acceptée par un PDA non déterministe peut ou peut ne pas être intrinsèquement ambiguë car il peut exister un DPDA (ou univoque CFG non ) pour elle.
  4. Un CFL généré par un CFG ambigu peut ou peut ne pas être intrinsèquement ambigu car il peut exister un CFG non ambigu (ou PDA déterministe ) pour lui.
  5. Une CFL générée par au moins une ambiguïté CFG est pas intrinsèquement ambiguë . (Il existe des DPDA pour cela.)
  6. Une grammaire non déterministe peut être ambiguë ou non .

PS:

  1. La réponse acceptée utilise des lignes comme «CFL est déterministe», «CFL déterministe», «CFL ne peut pas être déterministe», «A CFL non déterministe». Je suppose que les adjectifs «déterministes» et «ambigus» ne s'appliquent pas à CFL, mais à PDA et CFG (bien que l'adjectif «intrinsèquement ambigu» s'applique à CFL) Bien que je ne veuille pas critiquer la réponse originale, car j'ai moi-même appris crucial points de celui-ci. (En fait, j'ai littéralement copié collé quelques lignes de cette réponse.) Mais je pensais que cela devrait être rendu plus correct. J'ai donc essayé de mettre les choses plus clairement ici en deux parties: définitions et faits (j'aurais pu le rendre inutilement verbeux et long). Je suppose que j'aurais dû modifier la réponse d'origine, mais cela impliquera la suppression de nombreux points qui utilisent les lignes ci-dessus. Et je ne sais pas si cela en fera une modification valide car elle implique une réécriture complète.
  2. Notez que j'ai mis un mot quantitatif en gras et en italique pour mettre en évidence les différences comparatives dans les différentes définitions et faits. Les termes de définition sont uniquement en gras .
  3. Quelques points que j'ai faits moi-même, j'ai donc besoin de la confirmation de quelqu'un qui connaît bien ici la justesse de chaque point.
Maha
la source
PS 1 a tort: ​​il existe une définition standard pour les LFC déterministes / ambigus, à savoir, ils sont définis comme étant ceux pour lesquels tous les CFG sont déterministes / ambigus.
reinierpost
vient de réaliser le fait 7 est faux. De plus, le point 6 de l'avant-dernière liste est identique et incorrect.
Maha
En effet ... le déterminisme n'a pas d'ambiguïté à aucun moment pendant l' analyse, il est donc strictement plus fort que l'ambiguïté (c'est-à-dire l'ambiguïté même une fois l' analyse terminée).
reinierpost