12
$\begingroup$

I understand the following claims to be true:

  1. Two distinct derivations of a string in a given CFG may sometimes attribute the same parse tree to the string.
  2. When there are derivations of some string in a given CFG that attribute different parse trees, the CFG is ambiguous.
  3. Some context-free languages generated by ambiguous CFGs are also generated by unambiguous CFGs.
  4. Some languages are such that the only CFGs that can generate them (and there are some such) are ambiguous.

Q1. I understand it also to be undecidable whether an arbitrary CFG is ambiguous, in the sense of point 3 above. Or is it rather that it's undecidable whether a context-free language is ambiguous, in the sense of point 4? Or are both undecidable?

Q2. Which of points 1-4 become false when we replace "context-free" with "regular"? Are regular grammars and languages always unambiguous?

$\endgroup$
5
  • $\begingroup$ The languages you mention in point 4 are "Inherently ambiguous". For Q1, I think that it is undecidable whether the GRAMMAR is ambiguous. Thus Both 3 and 4 are undecidable. $\endgroup$
    – Lamine
    Commented Sep 20, 2013 at 15:25
  • $\begingroup$ Right, point 4 languages are called "inherently ambiguous". $\endgroup$
    – dubiousjim
    Commented Sep 20, 2013 at 16:46
  • 4
    $\begingroup$ Q1: both undecidable. Q2: 1 is not possible, because there is at most one non terminal appearing in any sentential form, thus any derivation is both leftmost and rightmost; 2 that's still true; 3 still true if you remove the ``also'' bit; 4 not true any more, for instance by determinizing your grammar you will get an unambiguous one. $\endgroup$
    – Sylvain
    Commented Sep 20, 2013 at 22:54
  • 1
    $\begingroup$ @Sylvain make that an answer? $\endgroup$ Commented Sep 21, 2013 at 0:36
  • $\begingroup$ @Sylvain, thanks, and yes make that an answer. Can I confirm I've understood? re 2: So there exists a regular grammar that can generate the same string with different parse trees? (I've since come across a reference to "ambiguous NFAs", but I'm not sure it's using "ambig" in the sense I am). Re 3 and 4, I think you're saying that some regular languages can be generated by ambiguous regular grammars, but will always also be generated by an unambig regular grammar too? $\endgroup$
    – dubiousjim
    Commented Sep 21, 2013 at 11:42

3 Answers 3

19
$\begingroup$

About Q1: Both the ambiguity problem (given a CFG, whether it is ambiguous) and the inherent ambiguity problem (given a CFG, whether its language is inherently ambiguous, i.e. whether any equivalent CFG is ambiguous) are undecidable. Here are the original references:


About Q2: A regular grammar is a "one-sided linear" context-free grammar, where at most one nonterminal appears in any rule right-part, and where that nonterminal is at the last (in right linear grammars) or first (in left linear grammars) position. Such grammars are easily translated into equivalent finite-state automata (roughly by considering each nonterminal as a state), which are unambiguous iff the regular grammar is unambiguous. The class of unambiguous regular grammars and unambiguous automata has been studied in particular by Stearns and Hunt (1985), who show that they enjoy tractable algorithms for the inclusion problem.

  1. About the relationship between derivations (i.e. sequences of rules applications $\beta A\gamma\Rightarrow \beta\alpha\gamma$ where $A\to\alpha$ is a rule of the grammar) and derivation trees (i.e. where a node labeled $A$ is the parent of a sequence of nodes $X_1,\dots,X_m$, where $A\to X_1\cdots X_m$ is a rule): in a general CFG, there can be different derivations, which visit the same derivation tree in different ways.

    These different derivations occur because one has a choice between applying a grammar rule in two different places in a sentential form: in a sentential form $\gamma A\eta B\theta$ with at least two nonterminals $A$ and $B$, one can apply $A\to\alpha$ first and obtain $\gamma\alpha\eta B\theta$, or $B\to\beta$ first and obtain $\gamma A\eta\beta\theta$, but applying the other rule will lead to the same $\gamma\alpha\eta\beta\theta$. Imposing leftmost (always deriving the leftmost nonterminal in any sentential form) or rightmost derivations imposes a fixed order for visiting derivation trees, and there is then a single derivation for a given derivation tree.

    In a linear context-free grammar, there is no such choice, since there is at most one nonterminal in any sentential form, and there is a single derivation for a given derivation tree, which is both leftmost and rightmost.

  2. Having two different parse trees with the same yield $w$ (sequence of leaves) is the definition of $w$ being ambiguous, it does not change when considering regular grammars. Alternatively, one can also ask for two different leftmost derivations. Note that a derivation in a one-sided grammar corresponds to an accepting run in its associated finite-state automaton, which is called ambiguous exactly in the same way: when there exist two different accepting runs for a given input $w$.

  3. and 4.$~$ If you take the finite-state automata view, it suffices to determinize your ambiguous automaton in order to obtain an unambiguous automaton for the same language: there will be a single run for any given word. This deterministic automaton is equivalent to an unambiguous regular grammar.

    To answer your comment: there exist ambiguous regular grammars, for instance $S\to A\mid B,\,A\to a,\,B\to a$ has two leftmost derivations for $a$: $S\Rightarrow A\Rightarrow a$ and $S\Rightarrow B\Rightarrow a$. An equivalent unambiguous grammar is $S\to a$.

About the relation with Q1: it is decidable whether a regular grammar is ambiguous (the inherent ambiguity problem is not very challenging on regular grammars, since the answer is invariably "no" without even looking at the input grammar). This can be checked in $O(|G|^2)$ using a squaring construction on its associated automaton: construct the product of the automaton with itself, and see whether some state $(q,q')$ with $q\neq q'$ is accessible and co-accessible. The oldest reference I know for this idea is a paper by Even (1965).

$\endgroup$
1
$\begingroup$

Q1. Everything is undecidable since the question if grammar $G$ produces language $\Sigma^*$ (containing all words) or not is undecidable. But if you have some specific grammar, like grammar constructed by deterministic PDA, the questions are decidable, but it's a very boring case.

I didn't quite get about what kind of languages you talk in 4. Every CF-language has an ambiguous grammar.

Q2. Everything is decidable if you have a deal with a regular grammar. You just should construct minimal DFA and using it you can construct unambiguous grammar. If you have a deal with regular language defined by the CF-grammar, the answer is no — see Q1.

$\endgroup$
9
  • $\begingroup$ Thanks, good clarification re Q2. Questions about a regular language may be decidable if the language is specified by a regular grammar; but that doesn't yet mean they're decidable if the language is specified by a CFG---that's what you're saying, right? So do we know it to be the case that questions about ambiguity and so on which are undecidable for arbitrary CFGs are also undecidable when restricted to those CFGs that happen to generate regular languages? $\endgroup$
    – dubiousjim
    Commented Sep 20, 2013 at 16:50
  • $\begingroup$ Not may be, but they are always decidable. I mean when you have a deal with a language described by a regular grammar — the subclass of CFG, any question you like is decidable. But some nonregular CFG can produce a regular language, and it's undecidable even to verify if CFG produces a regular language. $\endgroup$ Commented Sep 20, 2013 at 17:00
  • 2
    $\begingroup$ @alexandr-rubtsov "When you deal with a language described by a regular grammar, any question you like is decidable". This looks like an over optimistic statement... $\endgroup$
    – J.-E. Pin
    Commented Sep 20, 2013 at 17:40
  • $\begingroup$ Thanks, I meant "may be" in its rhetorical function, not in the sense of "who knows?" $\endgroup$
    – dubiousjim
    Commented Sep 20, 2013 at 17:41
  • $\begingroup$ @J.-E.Pin yes I should have been more delicate and say something like «all natural questions such as ambiguity». $\endgroup$ Commented Sep 20, 2013 at 19:03
0
$\begingroup$

It depends on whether you substitute 'context-free' with 'regular' only in front of 'language(s)', or also in front of 'grammar(s)'.

All regular languages are generated by regular grammars, and in particular, by unambiguous regular grammars, e.g. LL(1) right-regular grammars, which are all unambiguous.

$\endgroup$

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.