Ambiguïté dans les langues régulières et sans contexte

Je comprends que les affirmations suivantes sont vraies:

1. Deux dérivations distinctes d'une chaîne dans un CFG donné peuvent parfois attribuer le même arbre d'analyse à la chaîne.
2. Lorsqu'il existe des dérivations d'une chaîne dans un CFG donné qui attribuent différents arbres d'analyse, le CFG est ambigu.
3. Certains langages sans contexte générés par des CFG ambigus sont également générés par des CFG non ambigus.
4. Certaines langues sont telles que les seuls CFG qui peuvent les générer (et il en existe) sont ambigus.

Q1. Je comprends également qu'il soit indécidable qu'un CFG arbitraire soit ambigu, au sens du point 3 ci-dessus. Ou est-ce plutôt qu'il est indécidable qu'une langue sans contexte soit ambiguë, au sens du point 4? Ou sont-ils tous deux indécidables?

Q2. Lequel des points 1 à 4 devient faux lorsque nous remplaçons «sans contexte» par «normal»? Les grammaires et les langues régulières sont-elles toujours sans ambiguïté?

À propos de Q1: Le problème d' ambiguïté (étant donné un CFG, s'il est ambigu) et le problème d' ambiguïté inhérent (étant donné un CFG, si son langage est intrinsèquement ambigu, c'est-à-dire si un CFG équivalent est ambigu) sont indécidables. Voici les références originales:

• L'indécidabilité de l'ambiguïté a été prouvée par Cantor (1962) , Floyd (1962) et Chomsky et Schützenberger (1963) . Les épreuves dans les manuels réduisent généralement du problème de correspondance postérieure.
• L'indécidabilité de l'ambiguïté inhérente a été prouvée par Ginsburg et Ullian (1966) .

À propos de Q2: Une grammaire régulière est une grammaire sans contexte "linéaire unilatérale", où au plus un non terminal apparaît dans n'importe quelle partie droite de la règle, et où ce terminal n'est pas en dernier (dans les grammaires linéaires droites ) ou en premier (dans grammaires linéaires gauche) position. De telles grammaires sont facilement traduites en automates équivalents à états finis (en gros en considérant chaque non-terminal comme un état), qui sont sans ambiguïté si la grammaire régulière est sans ambiguïté. La classe des grammaires régulières sans ambiguïté et des automates sans ambiguïté a été étudiée en particulier par Stearns et Hunt (1985) , qui montrent qu'ils apprécient les algorithmes exploitables pour le problème d'inclusion.

1. À propos de la relation entre les dérivations (c'est-à-dire les séquences d'applications de règles où A → α est une règle de la grammaire) et les arbres de dérivation (c'est-à-dire où un nœud étiqueté A est le parent d'une séquence de nœuds X 1 , … , X m , où A → X 1 ⋯ X m est une règle): dans un CFG général, il peut y avoir différentes dérivations, qui visitent le même arbre de dérivation de différentes manières.$\beta A\gamma\Rightarrow \beta\alpha\gamma$$A\to\alpha$$A$$X_1,\dots,X_m$$A\to X_1\cdots X_m$

   Ces différentes dérivations se produisent parce que l'on a le choix entre appliquer une règle de grammaire à deux endroits différents dans une forme sententielle: sous une forme sententielle avec au moins deux non terminaux A et B , on peut appliquer A → α d' abord et obtenir γ α η B θ , ou B → β d' abord et obtenez γ A η β θ , mais l'application de l'autre règle conduira au même γ α η β θ . Imposant$\gamma A\eta B\theta$$A$$B$$A\to\alpha$$\gamma\alpha\eta B\theta$$B\to\beta$$\gamma A\eta\beta\theta$$\gamma\alpha\eta\beta\theta$ plus à gauche(dériver toujours le non terminal le plus à gauche sous n'importe quelle forme sententielle) ou les dérivations les plus à droite imposent un ordre fixe pour visiter les arbres de dérivation, et il y a alors une seule dérivation pour un arbre de dérivation donné.

   Dans une grammaire linéaire sans contexte, il n'y a pas un tel choix, car il y a au plus un non terminal dans n'importe quelle forme sententielle, et il y a une seule dérivation pour un arbre de dérivation donné, qui est à la fois à gauche et à droite.

2. Avoir deux arbres d'analyse différents avec le même rendement (séquence de feuilles) est la définition de w ambiguë, elle ne change pas lorsque l'on considère des grammaires régulières. Alternativement, on peut également demander deux dérivations à gauche différentes. Notez qu'une dérivation dans une grammaire unilatérale correspond à un cycle d'acceptation dans son automate à états finis associé, qui est appelé ambigu exactement de la même manière: lorsqu'il existe deux cycles d'acceptation différents pour une entrée w donnée .$w$$w$$w$

3. et 4. Si vous prenez la vue des automates à états finis, il suffit de déterminer votre automate ambigu afin d'obtenir un automate sans ambiguïté pour la même langue: il y aura une seule exécution pour un mot donné. Cet automate déterministe équivaut à une grammaire régulière non ambiguë.$~$

   Pour répondre à votre commentaire: il existe des grammaires régulières ambiguës, par exemple a deux dérivations les plus à gauche pour a : S ⇒ A ⇒ a et S ⇒ B ⇒ a . Une grammaire non ambiguë équivalente est S → a .$S\to A\mid B,\,A\to a,\,B\to a$$a$$S\Rightarrow A\Rightarrow a$$S\Rightarrow B\Rightarrow a$$S\to a$

À propos de la relation avec Q1: il est possible de déterminer si une grammaire régulière est ambiguë (le problème d'ambiguïté inhérent n'est pas très difficile sur les grammaires régulières, car la réponse est toujours «non» sans même regarder la grammaire d'entrée). Cela peut être vérifié dans utilisant une construction quadratique sur son automate associé: construire le produit de l'automate avec lui-même, et voir si un état ( q , q ′ ) avec q ≠ q ′ est accessible et co -accessible. La référence la plus ancienne que je connaisse pour cette idée est un article d' Even (1965) .$O(|G|^2)$$(q,q')$$q\neq q'$

$G$$\Sigma^*$

Je ne sais pas vraiment quel genre de langues vous parlez en 4. Chaque langue CF a une grammaire ambiguë.

Q2. Tout est décidable si vous avez un accord avec une grammaire régulière. Vous devez simplement construire un DFA minimal et en l'utilisant, vous pouvez construire une grammaire non ambiguë. Si vous avez un accord avec le langage normal défini par la grammaire CF, la réponse est non - voir Q1.

Cela dépend si vous remplacez «sans contexte» par «régulier» uniquement devant «langue (s)», ou également devant «grammaire (s)».

Toutes les langues régulières sont générées par des grammaires régulières , et en particulier par des grammaires régulières non ambiguës, par exemple les grammaires LL (1) à droite régulière, qui sont toutes sans ambiguïté.