Proof of inherent ambiguity?
Dave Ohlsson
A context-free grammar is said to be ambiguous if at least one string
in the context-free language defined by that grammar has more than one
parse tree with that grammar.
A context-free language is said to be inherently ambiguous if all the
context-free grammars of that language are ambiguous.
Now, I wonder how one can prove inherent ambiguity.
Could anyone give an example of an inherently ambiguous context-free
language AND the proof that that language is inherently ambiguous?
-- dave
Nathan Sanders
> Could anyone give an example of an inherently ambiguous context-free
> language AND the proof that that language is inherently ambiguous?
I think the following might be what you are looking for:
L = {a^i b^j c^k | i=j or j=k}
Looking at strings like aabbcc, aaabbbccc, it seems that every grammar
must have at least two different parse trees, one for matching a's and
b's with arbitrary trailing c's, and one for matching b's and c's with
arbitrary preceding a's.
I'm not sure about a formal proof, though. I'm a bit rusty!
Nathan
--
Nathan Sanders
Linguistics Program nsan...@wso.williams.edu
Williams College http://wso.williams.edu/~nsanders
Williamstown, MA 01267
Rafael 'Dido' Sevilla
> Could anyone give an example of an inherently ambiguous context-free
> language AND the proof that that language is inherently ambiguous?
Do you have access to a copy of the original 1979 edition of the
Cinderella Book (Introduction to Automata Theory, Languages, and
Computation, by John Hopcroft and Jeffrey Ullman)? If memory serves
correctly, at the end of the chapter on CFL's and PDA's Hopcroft and
Ullman present an inherently ambiguous CFL and a proof of inherent
ambiguity. I'm not sure, but I'm afraid that it may have been one of
the things cut out in the 2000 edition of the Cinderella Book (it's
already in a starred "optional" section in the old edition).
--
dido
Te capiam, cuniculus sceleste!
Torben Ægidius Mogensen
> Could anyone give an example of an inherently ambiguous context-free
> language AND the proof that that language is inherently ambiguous?
The standard example of a language with inherent ambiguity is
L = L1 U L2, where
L1 = {a^m b^m c^n | m,n>0}
L2 = {a^m b^n c^n | m,n>0}
This is clearly context free, e.g. by the grammar
S -> S1 | S2
S1 -> A1 C
S2 -> A B1
A1 -> a b | a A1 b
B1 -> b c | b B1 c
C -> c | c C
A -> a | a C
The intersection of L1 and L2 is {a^m b^m c^m | m>0}. Any string in
the intersection will, obviously, have two syntax trees by the above
grammar, but this does not prove inherent ambiguity.
However, {a^m b^m c^m | m>0} is not a context free language, so you
can argue that no context free grammar can decide which way to parse
strings in the intersection, so there will always be ambiguity. This
is not a stringent proof, but a formal proof can follow the same idea.
Torben
Brian M. Scott
<dave_...@hotmail.com> wrote in sci.lang:
[...]
> Could anyone give an example of an inherently ambiguous context-free
> language AND the proof that that language is inherently ambiguous?
The language
{a^n b^n c^m d^m : n, m in N} U {a^m b^n c^n d^m : n, m in N}.
context-free and inherently ambiguous. The proof is long and
tedious and depends on the fact that there will always be two
different parse trees for some of the strings in the intersection
of the two pieces of the language. I believe that it can be
found in Hopcroft and Ullman, Introduction to Automata Theory.
Brian
Rick Decker
> A context-free language is said to be inherently ambiguous if all the
> context-free grammars of that language are ambiguous.
>
> Now, I wonder how one can prove inherent ambiguity.
>
> Could anyone give an example of an inherently ambiguous context-free
> language AND the proof that that language is inherently ambiguous?
The canonical example is
{a^n b^n c^m d^m | n, m >= 0} \union {a^n b^m c^n d^m | n, m >= 0}
the proof is a bit tricky, but you shouldn't have trouble
finding references to it. I got 156,000 hits from Google on "inherent
ambiguity."
Regards,
Rick
Michael J. Fromberger
Others have given you some examples of languages which are inherently
ambiguous. More generally, you might also find the following result
interesting:
W. G. Ogden, "A Helpful Result for Proving Inherent Ambiguity"
in Mathematical Systems Theory, Vol. 2, #3 (1969), pp. 191--194.
The abstract reads:
"It is shown that there is no `partial algorithm' (effective
procedure that may fail to terminate) by which, given a context free
grammar, one can always find an unambiguous context free grammar
generating the same language if such an unambiguous grammar exists.
The argument turns on the degree of unsovability of the inherent
ambiguity problem for context free languages."
The paper is available from ACM:
http://portal.acm.org/citation.cfm?id=800169.805417
Cheers,
-M
--
Michael J. Fromberger | Lecturer, Dept. of Computer Science
http://www.dartmouth.edu/~sting/ | Dartmouth College, Hanover, NH, USA
Harlan Messinger
>dave_...@hotmail.com (Dave Ohlsson) writes:
>
>> Could anyone give an example of an inherently ambiguous context-free
>> language AND the proof that that language is inherently ambiguous?
>
>The standard example of a language with inherent ambiguity is
>
> L = L1 U L2, where
> L1 = {a^m b^m c^n | m,n>0}
> L2 = {a^m b^n c^n | m,n>0}
>
>This is clearly context free, e.g. by the grammar
>
> S -> S1 | S2
> S1 -> A1 C
> S2 -> A B1
> A1 -> a b | a A1 b
> B1 -> b c | b B1 c
> C -> c | c C
> A -> a | a C
Rather, A -> a | a A, correct?
--
Harlan Messinger