1
$\begingroup$

Consider the context-free grammar G = ({a, +, ∗}, {S}, {S → SS+ | SS∗ | a}, {S}) and consider the string aa+a* generated by this grammar.

Is this grammar unambiguous?

I have browsed the Internet and I have found that there is no standard procedure for proving if a grammar is unambiguous or not. But sometimes induction on length of the string or maybe length of the derivations works. I think in this question I can do something via length of sentential forms but I am not sure if its rigorous or not.

My approach: induction on length of sentential forms

Base case: length=1 then it has to be S -> a hence unambiguous.
Induction step: for length <= n assume all sentential forms are unambiguous. Consider a sentential form ww'. So here w can be either S or a. If a then done since unique derivation else if S then only possibility is that there has to be SS+ or SS* hence we know S produces these unambiguously and the rest is unambiguous by hypothesis hence proved.

This seems more of a cyclic argument to me so I would be glad if someone could help me out.

By the way, what is the language generated by a grammar?

In this case, I think that it's the language that does postfix operation on addition and multiplication that is being described here. But how do we generalise for grammars?

$\endgroup$
7
  • 1
    $\begingroup$ Please ask only one question per post. $\endgroup$
    – D.W.
    Feb 4 at 22:00
  • $\begingroup$ Yes, the language consists of reversed Polish notations where each number is denoted by the single character "a". $\endgroup$
    – John L.
    Feb 7 at 6:51
  • $\begingroup$ I can derive aa in two ways. $\endgroup$
    – gnasher729
    Feb 7 at 7:10
  • $\begingroup$ I see… * and + are used as actual symbols instead of part of the grammar. $\endgroup$
    – gnasher729
    Feb 7 at 7:12
  • $\begingroup$ "there has to be SS+ or SS* hence we know S produces these unambiguously." Which S produces what? Had you specified clearly what are they referring to, you will see there is some significant gap. $\endgroup$
    – John L.
    Feb 7 at 10:52

2 Answers 2

0
$\begingroup$

$L(G)$ is the set of all p-expressions

Let an operator mean either $+$ or $*$. In order to characterize the strings generated by $G$, we may observe the number of operators and the number of $a$'s in a string.

Call a string $w$ over alphabet $\{a, +, *\}$ a p-expression if

  • $w$ is non-empty, and
  • there are at least as many operators as $a$'s in each proper suffix of $w$ while there are one less operators than $a$'s in $w$. (In particular, $w$ ends with an operator and starts with two $a$'s unless $w=a$.)

Claim: $L(G)$ is the set of all p-expressions.
Proof: Use structural induction. This is an easy exercise for the readers.

$G$ is unambiguous

Proof: Let us show that $w\in L(G)$ has a unique parse tree using induction on $|w|$.

  • Base case, $|w|=1$. Then $w$ must be $a$. $S\to a$ is the only derivation for $w$.
  • As induction hypothesis, assume the proposition is true for $|w|\le n$.
    Let $|w|=n+1$. WLOG, suppose $w$ ends with $+$. So the first step in the derivation for $w$ must be $$S\to SS+.$$
    Let $w_1$ be the string produce by the first $S$ on the right hand side and $w_2$ be the string produced by the second $S$ so that $w=w_1w_2+$. Note that $w_1, w_2\in L(G)$.
    Scanning $w_1w_2+$ from right to left character by character, let us track the difference of the number of operators and the number of $a$'s scanned. The claim above implies the last scanned character of $w_2$ must be the character at which that difference have dropped to 0 for the first time.
    So $w_2$ is determined uniquely by $w$. Hence $w_1$ is also determined uniquely by $w$.
    By induction hypothesis, there is a unique parse tree for $w_1$ and for $w_2$. Hence, there is a unique parse tree for $w$. $\quad\checkmark$

Inspect $G$ reversed

Here is another way to show $G$ is unambiguous, which may appear simpler for readers with more experience.

Let $G^r$ be $G$ with production rules reversed, i.e., $$G^r=(\{a,+, *\}, \{S\}, \{S\to +SS, S\to *SS, s\to a\}, \{S\}).$$ It is easy to see that $G$ is unambiguous iff $G^r$ is unambiguous.

With some simple routine computation, we can obtain the $LL(1)$ parsing-table of $G^r$, $$\begin{array} {|c|c|c|c|}\hline &{\\\$} &+ & * & a \\\hline S & &S\to +SS &S\to *SS & S\to a \\\hline \end{array}$$ As an $LL(1)$ grammar, $G^r$ is unambiguous. Hence, $G$ is ambiguous as well.

More generally, we can prove that a context-free grammar is unambiguous if all production rules end with different terminals.

An exercise

Prove $(\{0, 1,+, *\},$ $\{S, B\},$ $\{S\to SS+,$ $S\to SS*,$ $S\to B,$ $B\to 0B,$ $B\to 1B,$ $B\to 0,$ $B\to 1\},$ $\{S\})$ is an unambiguous grammar.

$\endgroup$
2
  • $\begingroup$ John, maybe the exercise has a typo? The nonterminal B is not generating. $\endgroup$
    – Tonita
    Feb 8 at 17:16
  • $\begingroup$ @Tonita, thanks, updated. $\endgroup$
    – John L.
    Feb 8 at 17:29
1
$\begingroup$

I would like to suggest another easy method to prove that the grammar $G$ is unambiguous. We can use the LR(0) parsing property to do so.

The language $L(G)$ is not prefix-free. If we add the endmarker $\\\$$ to the language, thus introducing a new initial nonterminal $S'$ and the rule $S'$ $\rightarrow$ $S$ $\\\$$ then the prefix property is satisfied. If the resulting grammar $G'$ is LR(0) then the initial grammar is necessarily unambiguous, otherwise we would get a parsing conflict for some word in $L(G')$. The LR(0)-property of $G'$ can be easily proven by constructing the corresponding finite state automaton.

Btw, this method does not provide a criterion of unambiguety, it gives only a sufficient condition. There are some unambiguous grammars that generate non-deterministic CFLs (the most famous example is the grammar generating even palindromes).

$\endgroup$
1
  • $\begingroup$ Nice, with endmarker added $G$ does become LR(0) $\endgroup$
    – John L.
    Feb 12 at 23:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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