Existe-t-il des langues dépourvues de contexte, ambiguës et déterministes?

36

Appelons un langage déterministe sans contexte si et seulement si il peut être accepté par un automate push-down déterministe, et non déterministe autrement.

Appelons un langage dépourvu de contexte intrinsèquement ambigu si et seulement si toutes les grammaires sans contexte qui génèrent le langage sont ambiguës et non ambiguës sinon.

Un exemple de langage déterministe et non ambigu est le langage: Un exemple de langage non déterministe et non ambigu est le langage:

{a^{n} b^{n} \in {a, b}^{*} | n \geq 0}

$\{a^{n}b^{n} \in \{a, b\}^{*} | n \ge 0\}$

{w \in {a, b}^{*} | w = w^{R}}

$\{w \in \{a, b\}^{*} | w = w^{R}\}$

D'après Wikipedia , un exemple de langage dépourvu de contexte intrinsèquement ambigu est constitué par l'union suivante des langages dépourvus de contexte, qui doivent également être dépourvus de contexte:

L = {a^{n} b^{m} c^{m} d^{n} \in {a, b, c, d}^{*} | n, m \geq 0} \cup {a^{n} b^{n} c^{m} d^{m} \in {a, b, c, d}^{*} | n, m \geq 0}

$L = \{a^{n}b^{m}c^{m}d^{n} \in \{a, b, c, d\}^{*} | n, m \ge 0\} \cup \{a^{n}b^{n}c^{m}d^{m} \in \{a, b, c, d\}^{*} | n, m \ge 0\}$

Maintenant pour les questions:

Sait-on s'il existe un langage dépourvu de contexte, déterministe et intrinsèquement ambigu? Si oui, y a-t-il un exemple (facile)?
Sait-on s’il existe un langage non-contextuel, non-déterministe et intrinsèquement ambigu? Si oui, y a-t-il un exemple (facile)?

Clairement, puisqu’il existe un langage dépourvu de contexte et ambigu de manière inhérente ( est un exemple), la réponse à l’une de ces questions est simple si l’on sait si est déterministe ou non déterministe. Je suppose également qu'il est vrai que s'il existe un déterminisme, il en existe forcément un non déterministe ... mais j'ai déjà été surpris. Les références sont appréciées, et des excuses d’avance si c’est un résultat connu et célébré (auquel cas je ne suis absolument pas au courant). $L$ $L$

formal-languages automata formal-grammars pushdown-automata Patrick87
la source

30

Si un langage est déterministe, il est accepté par un automate poussoir déterministe, ce qui signifie qu'il existe une grammaire LR (1) décrivant le langage, et comme chaque grammaire LR (1) est sans ambiguïté, cela signifie que ne peut pas être intrinsèquement ambigu. Knuth l'a prouvé dans son article dans lequel il a présenté LR (1) ( De la traduction des langues de gauche à droite ). $L$ $L$

Une langue peut être décrite par une grammaire sans contexte si et seulement si elle peut être reconnue par un automate non déterministe. En tant que cas particulier, les automates non déterministes peuvent analyser les grammaires dépourvues de contexte intrinsèquement ambiguës.

Pour conclure, tout automate à bascule déterministe est également non déterministe (c'est le cas pour à peu près tout ce qui peut être non déterministe, pour une définition raisonnable du non déterminisme).

Alex ten Brink
la source

+1 pour la référence pour le fait que toutes les LFC déterministes ne sont pas ambiguës en soi. En fait, cela répond également à l’autre question: étant donné qu’il existe un langage ambigu intrinsèquement, et qu’il n’est pas déterministe, il doit être non déterministe (remarquez que ma définition de LFC non déterministe n’est pas standard, car elle exclut les LFC déterministes; c’est de ma faute. pour abuser de la terminologie). En tout état de cause, vous avez donné un exemple pour la question (2) et montré que la question (1) est une impossibilité. Je vais attendre de voir si quelqu'un élabore plus, mais sinon, je l'accepterai comme étant correct. Merci!

Patrick87

0

En lisant wikipedia & la réponse & votre commentaire, référez-vous à la question (Q2), toutes les LFC par nature ambiguës doivent être non déterministes sous la définition standard (y compris votre propre exemple!). a traversé cette référence

Certaines langues sans contexte par nature ambiguë / Shamir & probablement d’autres sont étudiées dans la littérature.

vzn
la source

Existe-t-il des langues dépourvues de contexte, ambiguës et déterministes?

Réponses: