2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\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 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.