# Proving a LL(1) equivalent grammar doesn't exist

Consider the following CFG

$$S \rightarrow \epsilon\ |\ aSbS\ |\ bSaS$$

How can we prove formally that an equivalent $$LL(1)$$ grammar does not exist. I feel that intuitively an equivalent $$LL(1)$$ grammar doesn't exist, but I'm unable to prove this formally.

## 1 Answer

The language for the grammar in the question is the set of all words with equal number of $$a$$'s and $$b$$'s.

I am afraid your intuition is incorrect. Here is an $$LL(1)$$ grammar for it.

$$S \to aAbS \mid bBaS \mid \epsilon$$
$$A \to aAb \mid \epsilon$$
$$B \to bBa \mid\epsilon$$

Here is some statistics about the above $$LL(1)$$ grammar. $$\begin{array} {|c|c|c|c|} \hline \text{nonterminal} &\text{first set} &\text{follow set} &\text{nullable} &\text{endable}\\\hline S &a\ b &\emptyset &\text{yes} &\text{yes}\\\hline A &a &b &\text{yes} &\text{no}\\\hline B &b &a &\text{yes} &\text{no}\\\hline \end{array}$$

Here is the parsing table. $$\begin{array} {|c|c|c|c|}\hline &a & b &\ \\\hline S &S\to aAbS &S\to bBaS &S\to \epsilon\\\hline A &A\to aAb &A\to \epsilon\quad\ & \\\hline B &B\to \epsilon\quad\ &B\to bBa & \\\hline \end{array}$$

Exercise. Show that both the grammar in the question and the grammar in this answer generate the language of words with equal number of $$a$$'s and $$b$$'s.

• Thanks a lot! I realize my intuition was wrong. – user104014 Jan 31 at 7:54