# Confusion related to the union of two type 3 grammar

I have this confusion. Lets say I have two languages produced by type 3 grammar such that

L(G1) = <Vn1,Vt,P1,S1>
L(G2) = <Vn2,Vt,P2,S2>


I need to find a type3 grammar G3 such that

L(G3) = L(G1)U L(G2)

I can't use $S3 \rightarrow S1$ and $S3 \rightarrow S2$ rule in this new G3 to get the union, because the production is not type 3 as well. So what should I do?

-
Those productions are type $3$: they have a single non-terminal on the lefthand side. – Brian M. Scott Sep 20 '12 at 1:48
@Brian. But in type 3 grammar the production rules should be like $S \rightarrow aA$ or $S \rightarrow a$ where A and S are non terminals and a is terminal. So if I had $S3 \rightarrow S1$, then it is not type 3 – user12331 Sep 20 '12 at 2:58
Sorry: I was thinking context-free. You’re right. Hang on a minute and I’ll write you a quick answer. – Brian M. Scott Sep 20 '12 at 3:06
@Brian. I think if L(G1) has start state lets say $S1 \rightarrow aA$ and L(G2) has $S2 \rightarrow aB$ then L(G3) will have $S3 \rightarrow aA$ and $S3 \rightarrow aB$. Since both G1 and G2 are type 3, this will follow I guess – user12331 Sep 20 '12 at 3:17
You have the right idea, but you have to be a bit more careful: you want to make sure that the grammar doesn’t allow derivations that start out with $G_1$ productions and then switch to $G_2$ productions. – Brian M. Scott Sep 20 '12 at 3:32

First note that a regular grammar can be modified to make an equivalent regular grammar in which the initial symbol does not appear on the righthand side of any production. A simple example is converting the grammar whose productions are $S\to\lambda$ and $S\to aS$ into one whose productions are $S\to\lambda$, $S\to aX$, $X\to aX$, and $X\to\lambda$. I’ll let you think about how to do this in general, and from here on I’ll assume that $G_1$ and $G_2$ have this property.
If the original grammars are $G_1=\langle N_1,\Sigma,P_1,S_1\rangle$ and $G_2=\langle N_2,\Sigma,P_2,S_2\rangle$, construct $G$ as follows. First note that you can assume that $N_1\cap N_2=\varnothing$: if this is not the case, replace each non-terminal $\nu\in N_2$ by a new symbol $\nu'$ that is not in $N_1\cup\Sigma$.
Now let $S$ be a new non-terminal symbol, and let $N=N_1\cup N_2\cup\{S\}$; the new grammar will be $G=\langle N,\Sigma,P,S\rangle$, where $P$ is constructed as follows. First, $P$ contains every production in $P_1\cup P_2$ that does not contain $S_1$ or $S_2$. If $P_1$ contains a production $S_1\to\alpha$, replace it with $S\to\alpha$. Similarly, if $P_2$ contains a production $S_2\to\alpha$, replace it with $S\to\alpha$. This is exactly what you suggested in your comment above, and it works, once you’ve made sure that $N_1$ and $N_2$ are disjoint and that no production has an initial symbol on the righthand side.
In case it isn’t quite clear, the problem with having $S_1$, say, on the righthand side of a production $A\to aS_1$ in $P_1$ is that you’d get $A\to aS$ in $P$, and then you could continue the derivation with productions that originated in $G_2$. Thus, you could end up with a word whose derivation was half in $G_1$ and half in $G_2$, the word itself being in neither language.