# Grammar to Language

Having:

\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

• 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.) – 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$.

• 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? – user9801 Aug 23 '13 at 20:45
• You're almost there, but can you explain the first part "a|ab|ba|ac|ca|aa"? – 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


Factor:

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