<p>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.</p>

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

<p>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. </p>

CC BY-SA 3.0
2013-09-20T16:50:15.933Z
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?
dubiousjim
CC BY-SA 3.0
2013-09-20T17:00:08.487Z
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.
Alexander Rubtsov
CC BY-SA 3.0
2013-09-20T17:40:20.690Z
@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...
J.-E. Pin
CC BY-SA 3.0
2013-09-20T17:41:03.507Z
Thanks, I meant "may be" in its rhetorical function, not in the sense of "who knows?"
dubiousjim
CC BY-SA 3.0
2013-09-20T19:03:02.623Z
@J.-E.Pin yes I should have been more delicate and say something like «all natural questions such as ambiguity».
Alexander Rubtsov
CC BY-SA 3.0
2013-09-20T22:55:50.617Z
Could you clarify the relation between the universality problem and the ambiguity and inherent ambiguity problems?
Sylvain
CC BY-SA 3.0
2013-10-30T16:30:15.417Z
Your answer is invalid: the question is about a particular kind of grammar, the [regular grammars](https://en.wikipedia.org/wiki/Regular_grammar).
reinierpost
CC BY-SA 3.0
2013-11-27T14:28:38.777Z
@reinierpost so what's wrong in my Q2-section answer? I agree that section Q1 is bad.
Alexander Rubtsov
CC BY-SA 3.0
2013-12-09T12:58:16.833Z
@Alexandr Rubtsov: hmmm, I must not have been reading carefully. It is correct, but I think you can word it more clearly.
reinierpost
CC BY-SA 3.0
2013-09-20T16:02:45.627Z
2013-09-20T16:08:59.497Z
2013-09-20T16:08:59.497Z
Alexander Rubtsov
<p>It depends on whether you substitute 'context-free' with 'regular' only in front of 'language(s)', or also in front of 'grammar(s)'.</p>

<p>All regular languages are generated by <a href="https://en.wikipedia.org/wiki/Regular_grammar" rel="nofollow">regular grammars</a>, and in particular, by unambiguous regular grammars, e.g. <a href="https://en.wikipedia.org/wiki/LL_parser" rel="nofollow">LL(1)</a> right-regular grammars, which are all unambiguous.</p>

CC BY-SA 3.0
2013-10-30T16:37:05.883Z
2013-10-30T16:37:05.883Z
reinierpost
<p>About Q1:
Both the <em>ambiguity</em> problem (given a CFG, whether it is ambiguous) and the <em>inherent ambiguity</em> 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:</p>

<ul>
<li>The undecidability of ambiguity was proved by <a href="http://dx.doi.org/10.1145/321138.321145">Cantor (1962)</a>, <a href="http://dx.doi.org/10.1145/368959.368993">Floyd (1962)</a>, and <a href="http://dx.doi.org/10.1016/S0049-237X(08)72023-8">Chomsky and Schützenberger (1963)</a>.  The proofs in textbooks typically reduce from the Post Correspondence Problem.</li>
<li>The undecidability of inherent ambiguity was proved by <a href="http://dx.doi.org/10.1145/321312.321318">Ginsburg and Ullian (1966)</a>.</li>
</ul>

<hr>

<p>About Q2:  A <em>regular</em> 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 <em>right linear</em> grammars) or first (in <em>left linear</em> 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 <a href="http://dx.doi.org/10.1137/0214044">Stearns and Hunt (1985)</a>, who show that they enjoy tractable algorithms for the inclusion problem.</p>

<ol>
<li><p>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 <em>visit</em> the same derivation tree in different ways.</p>

<p>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 <em>leftmost</em> (always deriving the leftmost nonterminal in any sentential form) or <em>rightmost</em> derivations imposes a fixed order for visiting derivation trees, and there is then a single derivation for a given derivation tree.</p>

<p>In a <em>linear</em> 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.</p></li>
<li><p>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 <em>ambiguous</em> exactly in the same way: when there exist two different accepting runs for a given input $w$.</p></li>
<li><p>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.</p>

<p>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$.</p></li>
</ol>

<p>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 <em>squaring</em> 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 <a href="http://dx.doi.org/10.1109/PGEC.1965.263996">Even (1965)</a>.</p>

CC BY-SA 3.0
2013-09-22T13:33:26.623Z
2013-09-22T13:33:26.623Z
Sylvain
<p>I understand the following claims to be true:</p>

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

<p>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?</p>

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

CC BY-SA 3.0
2013-09-20T15:25:53.337Z
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.
Lamine
CC BY-SA 3.0
2013-09-20T16:46:55.077Z
Right, point 4 languages are called "inherently ambiguous".
dubiousjim
CC BY-SA 3.0
2013-09-20T22:54:42.720Z
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.
Sylvain
CC BY-SA 3.0
2013-09-21T00:36:29.437Z
@Sylvain make that an answer?
Yuval Filmus
CC BY-SA 3.0
2013-09-21T11:42:53.680Z
@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?
dubiousjim
<fl.formal-languages><regular-language><context-free>
Ambiguity in regular and context-free languages
dubiousjim
# Ambiguity in regular and context-free languages

(Asked by: username_0 on 2013-09-20)

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?

**Tags:** fl.formal-languages, regular-language, context-free
> **Comments:**
> **username_1**: 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.  
> **username_0**: Right, point 4 languages are called "inherently ambiguous".  
> **username_2**: 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.  
> **username_3**: @Sylvain make that an answer?  
> **username_0**: @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?  

---

## 3 answers

### Answer by username_2 on 2013-09-22. Score: 19 | Accepted answer

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:

* The undecidability of ambiguity was proved by [Cantor (1962)](http://dx.doi.org/10.1145/321138.321145), [Floyd (1962)](http://dx.doi.org/10.1145/368959.368993), and [Chomsky and Schützenberger (1963)](http://dx.doi.org/10.1016/S0049-237X(08)72023-8). The proofs in textbooks typically reduce from the Post Correspondence Problem.
* The undecidability of inherent ambiguity was proved by [Ginsburg and Ullian (1966)](http://dx.doi.org/10.1145/321312.321318).

---

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)](http://dx.doi.org/10.1137/0214044), 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)](http://dx.doi.org/10.1109/PGEC.1965.263996).


---

### Answer by username_4 on 2013-09-20. Score: 1

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.

> **Comments:**
> **username_0**: 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?  
> **username_4**: 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.  
> **username_5**: @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...  
> **username_0**: Thanks, I meant "may be" in its rhetorical function, not in the sense of "who knows?"  
> **username_4**: @J.-E.Pin yes I should have been more delicate and say something like «all natural questions such as ambiguity».  
> **username_2**: Could you clarify the relation between the universality problem and the ambiguity and inherent ambiguity problems?  
> **username_6**: Your answer is invalid: the question is about a particular kind of grammar, the [regular grammars](https://en.wikipedia.org/wiki/Regular_grammar).  
> **username_4**: @reinierpost so what's wrong in my Q2-section answer? I agree that section Q1 is bad.  
> **username_6**: @Alexandr Rubtsov: hmmm, I must not have been reading carefully. It is correct, but I think you can word it more clearly.  

---

### Answer by username_6 on 2013-10-30. Score: 0

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](https://en.wikipedia.org/wiki/Regular_grammar), and in particular, by unambiguous regular grammars, e.g. [LL(1)](https://en.wikipedia.org/wiki/LL_parser) right-regular grammars, which are all unambiguous.


---

