Exercise 2.

We consider the alphabet $\Sigma$ = {a, b} and the grammar G below. Let L be the language generated by G over $\Sigma$.

G

$$\left\{\vphantom{ \begin{array}{rcl} S & \longmapsto & AB \\ A &... ...longmapsto & b B B \\ B & \longmapsto & {\varepsilon} \\ \end{array} }\right.$$$$\begin{array}{rcl} S & \longmapsto & AB \\ A & \longmapsto & a A... ...\\ B & \longmapsto & b B B \\ B & \longmapsto & {\varepsilon} \\ \end{array}$$

Give a grammar G' generating L $\setminus$ {$\varepsilon$} and with no $\varepsilon$-productions, that is no rules of the form X $\longmapsto$ $\varepsilon$, where $\varepsilon$ denotes the empty word. Is G' left-recursive?

Answer 2