Take the 2-minute tour ×
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.

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)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?

share|improve this question
    
What is your definition of type 3 grammar? Which productions are allowed? –  Yuval Filmus Sep 21 '12 at 4:43

1 Answer 1

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.

share|improve this answer

Your Answer

 
discard

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.