CFG production rules for multiple CFG's

551 Views Asked by At

I have the following 2 part question of which I can do the first part but am having trouble understanding the question for the second part. The first part asked for the production rules for $L_1=(a^nb^n |n\geq0)$, $P_1 = (S_1 \rightarrow aS_1b|\epsilon$).

The second part is:

Give a set $P_3$ of production rules for a CFG $G_3=((S_1,S_2,S_3), (a,b,c), P_1\cup P_2\cup P_3, S_3)$ which generates $L(G_1) \cdot L(G_2) = (xy | x \in L(G_1), y \in L(G_2))$

$L_2=(b^nc^n|n\geq0),$$P_1 = (S_2 \rightarrow bS_2c|\epsilon$)

So based on this $G_3$ generates $L(G_1) \cdot L(G_2) = (xy | x \in L(G_1), y \in L(G_2))$ and I need to give the production rules for this. But im having trouble understanding the notation i guess and cant see how to integrate $x$ into $L(G_1)$ and $y$ into $L(G_2).$ Is it a simple as $S_3 \rightarrow xS_3y|\epsilon$. Im not sure if anyone could explain it would be much appreciated.

1

There are 1 best solutions below

6
On

HINT: The key idea is the production $S_3\to S_1S_2$.

(And I think that you mean $P_1\cup P_2\cup P_3$ in the description of $G_3$.)