¿Existen lenguajes inherentemente ambiguos y deterministas libres de contexto?

36

Llamemos a un lenguaje determinista sin contexto si y solo si puede ser aceptado por un autómata determinista de empuje hacia abajo, y no determinista de lo contrario.

Llamemos a un lenguaje libre de contexto inherentemente ambiguo si y solo si todas las gramáticas libres de contexto que generan el lenguaje son ambiguas e inequívocas de lo contrario.

{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}\}$

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\}$

Now for the questions:

Is it known whether there exists a deterministic, inherently ambiguous context-free language? If so, is there an (easy) example?
Is it known whether there exists a nondeterministic, inherently ambiguous context-free language? If so, is there an (easy) example?

Clearly, since an inherently ambiguous context-free language exists ( $L$ is an example), the answer to one of these questions is easy, if it is known whether $L$ is deterministic or nondeterministic. I also assume that it's true that if there's a deterministic one, there's bound to be a nondeterministic one as well... but I've been surprised before. References are appreciated, and apologies in advance if this is a well-known, celebrated result (in which case, I'm completely unaware of it).

formal-languages automata formal-grammars pushdown-automata Patrick87
fuente

30

If a language $L$ is deterministic, it is accepted by some deterministic push-down automaton, which in turn means there is some LR(1) grammar describing the language, and as every LR(1) grammar is unambiguous, this means that $L$ cannot be inherently ambiguous. Knuth proved this in his paper in which he introduced LR(1) (On the Translation of Languages from Left to Right).

A language can be described by some context-free grammar if and only if it can be recognized by some nondeterministic automaton. As a special case of this, inherently ambiguous context-free grammars can be parsed by some nondeterministic automaton.

On a final note, any deterministic push-down automaton is also nondeterministic (this is the case for just about anything that can be nondeterministic, for a reasonable definition of nondeterminism).

Alex ten Brink
fuente

+1 for the reference for the fact that all deterministic CFLs are not inherently ambiguous. In fact, that answers the other question as well: since there is an inherently ambiguous language, and it's not deterministic, it must be nondeterministic (notice that my definition of nondeterministic CFL isn't standard, since it excludes deterministic CFLs; that's my fault for misusing terminology). In any event, you have given an example for question (2), and shown that question (1) is an impossibility. I'll wait and see if somebody elaborates more, but will otherwise accept this as correct. Thanks!

Patrick87

0

reading wikipedia & the answer & your comment on it, re (Q2) to state outright, all inherently ambiguous CFLs must be nondeterministic under the std defn (incl your own example!). ran across this ref

Some inherently ambiguous context-free languages / Shamir & likely others are studied in the literature.

vzn
fuente

¿Existen lenguajes inherentemente ambiguos y deterministas libres de contexto?

Respuestas: