3
$\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)L(G2)

I can't use $S3 \rightarrow S1S2$ to get the concatenaion, because the production is not type 3 as well. So what should I do?

  • 0
    What is your definition of type 3 grammar? Which productions are allowed?2012-09-21

1 Answers 1

2

First change one of the grammars, if necessary, to make sure that they have disjoint sets of non-terminal symbols.

If you’re allowing only productions of the forms $X\to a$ and $X\to Ya$, make the new grammar $G$ generate a word of $L(G_2)$ first and then a word of $L(G_1)$: replace every production of the form $X\to a$ in $G_2$ by the production $X\to S_1a$.

If you’re allowing only productions of the forms $X\to a$ and $X\to aY$, replace every production of the form $X\to a$ in $G_1$, by the production $X\to aS_2$.

If you’re allowing productions of both forms, you’re not talking about type $3$ grammars.