2
$\begingroup$

Is there any technique to prove that a given language L is not ambiguous context-free? Here I don't know that whether L is CFL or not.

Improve this question
$\endgroup$
2
  • 2
    $\begingroup$ For CFL, "the undecidability of inherent ambiguity was proved by Ginsburg and Ullian (1966)." in cstheory.stackexchange.com/questions/19102. Found with a call to google using : Context-free language inherent ambiguity undecidable. $\endgroup$
    – babou
    Commented Apr 20, 2015 at 8:41
  • $\begingroup$ I don't understand what you are trying to show. That $L$ is inherently ambiguous, that it is not? $\endgroup$
    – Raphael
    Commented Apr 20, 2015 at 8:50

2 Answers 2

Reset to default
5
$\begingroup$

Your question is strange. If you do not know what kind of language you have, the question may well be meaningless, as the concept of ambiguity can only be defined with respect to a known system of enumeration of the sentences of the language. There is none if the language is not Recursively Enumerable.

Thus it does not make sense to ask whether a language is ambiguous in general.

I take this as an opportunity for a little survey of these types of definitions.

In your case, if you specified that your language is context-free (but you did not), the question makes some more sense since CF languages have at least one CF grammar, which can be used as reference rewriting system to generate the sentences of the language (assuming you restrict to leftmost derivations, as canonical representatives of equivalence classes of derivations).

However, each CF language has actually an infinity of CF grammars generating it, and ambiguity has to be defined with respect to a single generation system. Hence the concept of ambiguity makes sense for the language of a given CFG with respect to that CFG, but does not make sense a priori for the langage alone.

However, computer science developed the concept of inherent ambiguity.

A CF language is inherently ambiguous iff all CF grammars generating that language are ambiguous.

It is however becoming common to say that a CF language is ambiguous to mean that it is inherenlty ambiguous.

Notes:

  1. Given any CF grammar G, it is trivial to give an ambiguous CF grammar G' that generates the same language. So, what can be interesting is not to know whether a CF language may have an ambiguous CF grammar (that is always possible), but whether it has only ambiguous CF grammars.

  2. This refers only to CF grammars. It is possible that an inherently ambiguous CF language can be generated unambiguously by a grammar that is not CF. For example, I would conjecture that there is an inherenlty ambiguous CF language that can be generated by an unambiguous Tree Adjoining Grammar (TAG) (but I do not know whether it is true or easy to check).

  3. This kind of knowledge organization framework can apply to other properties related to the generation or recognition process associated with a language. A good example is determinism of automata of a given family recognizing the language. Precision is always important: a language may be inherently non-deterministic with respect to a left-to-right PDA recognizer, but not when the PDA recognizer is right-to-left.

  4. This kind of framework, whether for ambiguity or other properties, can also be developed for other families of languages and enumeration mechanisms (possibly up to some notion of generative equivalence, such as the order of rule application in the case of CF grammar derivations).

Hence your question should be better phrased as:

If I am given a language L that is Context-Free, is there any technique to prove that it is not ambiguous.

It is even better if you say "... that it is not inherently ambiguous".

Note that even there, there is the implicit assumption that you refer to the leftmost derivations of CF grammars.

In the case of CF languages and grammars, you have many answers that you can find on the CS Theory site at the question Ambiguity in regular and context-free languages.

In particular:

  • it is undecidable whether a given CF grammar is ambiguous (1962-63, Cantor - Floyd - Chomsky and Schutzenberger)

  • it is undecidable whether a given CF language is inherently ambiguous (Ginsburg and Ullian - 1966).

Improve this answer
$\endgroup$
1
$\begingroup$

the general problem of determining whether a CFL is "inherently ambiguous" is undecidable (as mentioned/ cited in comments) but heuristics do exist and are an active area of research. see eg

Improve this answer
$\endgroup$
1
  • $\begingroup$ thanks @babou.But I don't know whether the given language L is context free or not.But I know that the given language L is not is not unambiguous context free.I want to know that whether the language L will be in the ambiguous CFL class or not. $\endgroup$
    – anand nayak
    Commented Apr 21, 2015 at 13:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.