Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
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
up vote 1 down vote accepted

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.