Derivation from grammar

Question

Given the grammar $G=(\{S, L_x, R_x, W_x\}, \{a,b\}, P, S)$ derive the words $abaaba$ and $aabbaabb$. $$ P=\left\{ \begin{align}S\phantom{{}_x R_y} &\to \epsilon \mid L_x R_x,\\ L_x \phantom{R_y} &\to x \mid L_x y W_y,\\ W_x y\phantom{{}_y} &\to y W_x,\\ W_x R_y &\to R_y x,\\ R_x \phantom{R_y} &\to x \\ \end{align}\right\}$$ with $x,y$ element of $\{a,b\}$. ($x$ and $y$ may or may not be equal)

Following the rules I always end up with words of the form $xx, xyxy, xyyxyy, \ldots$.
Am I allowed to replace each $y$ differently? Otherwise I don't see any way to get words like $abaaba$.

Answer 1

The grammar as given in your assignment is an abbreviation for the following expanded grammar:

$$P=\left \{ \begin{align} \begin{aligned} S &\to \epsilon, \\ S &\to L_a R_a, \\ S &\to L_b R_b, \\ \\ L_a &\to a, \\ L_a &\to L_a a W_a, \\ L_a &\to L_a b W_b, \\ \\ L_b &\to b, \\ L_b &\to L_b a W_a, \\ L_b &\to L_b b W_b, \\ \end{aligned}\qquad\begin{aligned} W_a a &\to a W_a, \\ W_a b &\to b W_a, \\ W_b a &\to a W_b, \\ W_b b &\to b W_b, \\[8pt] W_a R_a &\to R_a a, \\ W_a R_b &\to R_b a, \\ W_b R_a &\to R_a b, \\ W_b R_b &\to R_b b, \\[8pt] R_a &\to a\\ R_b &\to b\\ \end{aligned}\end{align}\right \}$$

So, yes, $x$ and $y$ need to be replaced consistently when you expand the shorthand notation. (And it's probably clear why the shorthand was used.)

Intuitively, what's happening here is that $S$ creates a left marker ($L_x$) and a right marker ($R_x$) which will eventually resolve to the same character. The left marker then expands to a sequence of $xW_x$ pairs, where $W_x$ is a "walker". The $W_x$s all walk to the right; when they finally hit the right marker, they deposit their payload after the right marker. This has the effect of creating two copies of the same string.

In an abbreviated form (combining derivation steps) you get something like this:

$$S\to L_aR_a\Rightarrow L_a b W_b a W_a R_a \Rightarrow L_a b a R_a b a \Rightarrow a b a a b a$$

Filling in the complete derivation would be a useful exercise. (Indeed, it's the exercise you've been asked to do.)