0

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.

dmnte
  • 257

1 Answers1

1

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

Brian M. Scott
  • 616,228
  • do you mean $S_3 \rightarrow S_1S_2$ ? – dmnte Jun 14 '16 at 09:40
  • @dmnte: I did indeed. Sorry about that: I'm typing on a Kindle at the moment, and it's a royal pain. – Brian M. Scott Jun 14 '16 at 09:43
  • Im still somewhat confused by the way they have written it but based on your hint and what is written in the question i would assume it might be $(S_3 \rightarrow S_1S_2),$$(S_1 \rightarrow x | \epsilon),$$(S_2 \rightarrow y|\epsilon)$ – dmnte Jun 14 '16 at 10:09
  • @dmnte: That's clearly not possible, because the description of $G_3$ specifies that the only terminal symbols are $a,b$, and $c$. The symbols $x$ and $y$ are used in the description of $L_3$ to represent whole words: they stand for strings of the forms $a^mb^m$ and $b^nc^n$, respectively. Note too that the set of productions of $G_3$ includes $P_2$ and $P_2$, i.e., it includes all of the productions that you already had for $G_1$ and $G_2$. – Brian M. Scott Jun 14 '16 at 10:21
  • oh ok that makes more sense, I didnt really understand the question completely to begin with. based on that wouldnt it be something like $(S_3 \rightarrow S_1S_2)$$(S_1 \rightarrow aS_1bS_2 | \epsilon)$$(S_2 \rightarrow bS_2c | \epsilon)$. that would give $a^nb^nb^mc^m$ – dmnte Jun 14 '16 at 10:57
  • @dmnte: You’ve got the right idea now, but not quite: the production $S_3\to S_1S_2$ already ensures that you get an $L_1$ word followed by an $L_2$ word, so you don’t need the $S_2$ in $S_1\to aS_1bS_2$. In fact, you don’t want it, because with it you get derivations like $$S_3\Rightarrow S_1S_2\Rightarrow aS_1bS_2S_2\Rightarrow abS_1S_2\Rightarrow abaS_1bS_2\Rightarrow ababS_2\Rightarrow ababbS_2c\Rightarrow ababbc;,$$ which is not in $L_3$. In fact all you need are the original productions of $G_1$ and $G_2$ together with the new $S_3\to S_1S_2$. – Brian M. Scott Jun 14 '16 at 18:19