$\qquad \begin{align} S &\to aT \\ T &\to a \mid UTV \\ U &\to ab \mid ba \\ V &\to ac \mid ca \end{align}$

What language would be generated by this?

How can I obtain an $LL(1)$ grammar using factorisation?

I've tried a number of combinations but do not get how to represent the UTV part:

Something like a|ab|ba|ac|ca|aa|a(ab|ba)^n a(ac|ca)^n

  • $\begingroup$ You have two separate questions here that require wildly different answers. Where does this come from? (You may find interesting material in our reference questions.) $\endgroup$ – Raphael Aug 26 '13 at 11:09

Hint: $U$ captures the regular expression $ab+ba$, $V$ captures $ac+ca$. The solution to an equation of the form $W \to Y | XWZ$ is $W = X^nYZ^n$.

  • $\begingroup$ I had a little think and came up with: a|ab|ba|ac|ca|aa|a(ab|ba)^n a(ac|ca)^n can someone confirm? $\endgroup$ – user9801 Aug 23 '13 at 20:45
  • $\begingroup$ You're almost there, but can you explain the first part "a|ab|ba|ac|ca|aa"? $\endgroup$ – Yuval Filmus Aug 23 '13 at 21:40

The problem is obviously with the T non-terminal because of the first set conflict, so let's work on it:

T -> a | UTV

Replace U:

T -> a | abTV | baTV 


T -> aP | baTV
P -> bTV | Eps

U has now become unreachable, so the LL(1) outcome:

S -> aT
T -> aP | baTV
P -> bTV | Eps
V -> ac | ca

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.