I'm trying to write a non-ambiguous context-free grammar that can generate the set of natural numbers, including the 0. My current solution is the following grammar:

$\mathcal{G}: S \rightarrow 0\ |\ ...\ |\ 9\ |\ 1S\ |\ ...\ |\ 9S$

From what I understand, there is not an algorithm to determine whether my guess is correct, thus only I—or you—can convince myself it is (or it is not, of course).

  • The set of natural numbers is produced by a regular language, and your grammar is right linear (and therefore regular), so in this particular case a proof is possible. – rici Sep 26 at 17:43

"From what I understand, there is not an algorithm to determine whether my guess is correct." It looks like your understanding is wrong.

There is no algorithm that determines whether any given formal language grammar is ambiguous context-free. There is no algorithm that determines whether any given formal language grammar is inherently ambiguous context-free. However, it is possible to decide many particular grammars is (inherently) ambiguous context-free or not by some algorithms. For example, the trivial algorithm that just outputs "ambiguous context-free" determines the grammar with rules $S\to A|B$, $A\to c$, $B\to c$ as ambiguous context-free. For example, the trivial algorithm that always outputs "not inherently ambiguous context-free" determines all regular grammars as not inherently ambiguous context-free.

As said by rici, your grammar is regular. There is an algorithm that can decide any given regular grammar is ambiguous or not. (Immediately by definition, a regular language is context-free.). As demonstrated by Dmitri Urbanowicz, your grammar is, in fact, not ambiguous.

As said by Dmitri Urbanowicz, your grammar is wrong since it cannot generate number 101. Here is a correct grammar, which can be shown to be non-ambiguous context-free.
$\quad S \to BT|A$
$\quad T \to AT|A$
$\quad A \to B|0$
$\quad B \to 1|2|3|4|5|6|7|8|9$

This grammar is unambiguous, because no pair of productions can lead to the same string. Since $S$ doesn't generate empty string, you either get different first characters or strings of different lengths.

Though this grammar is unable to generate $101$, for example.

A possibile solution is also:

$$ \begin{split} \mathcal{G}:\ & S \rightarrow 0\ |\ 1A\ |\ ...\ |\ 9A \\ & A \rightarrow \varepsilon\ |\ 0A\ |\ ...\ |\ 9A \end{split} $$

  • Indeed, this one can produce $101$! – cody Oct 1 at 14:39

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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