0
$\begingroup$

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

L(G1) =  L(G2) =  

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?

  • 0
    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.2012-09-20

1 Answers 1

1

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.