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.


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.

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

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.