# Confusion related to the type 3 grammar

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

L(G1) = <Vn1,Vt,P1,S1>


I need to find a type3 grammar G3 such that

L(G3) = [L(G1)]*

I can't use S3→S3S1 and S3→null rule in this new G3, because the production is not type 3 as well. So what should I do?

-
Are Vn1, Vt, P1, S1 just weirdly named terminals or do they stand for something? – Karolis Juodelė Sep 24 '12 at 19:34
they are the set of non-terminals, the set of terminals, the set of productions, and the initial symbol, respectively. – Mike Sep 24 '12 at 20:12

You have to arrange things so that whenever $G_1$ would generate a word, $G_3$ will either generate that word, or generate that word and start over. The obvious way to do that is to add to each production $X\to a$ of $G_1$ the production $X\to aS_3$. In addition, you will have to change every instance of $S_1$ to $S_3$ and add the production $S_3\to\lambda$, if $S_1\to\lambda$ wasn’t in the original grammar.

-
Is the null character in type 3 grammar? – Mike Sep 24 '12 at 20:10
@Mike: Yes: the type $3$ grammars are the regular grammars, which allow null productions. – Brian M. Scott Sep 24 '12 at 20:16
Thank you for the help – Mike Sep 24 '12 at 20:19
@Mike: You’re very welcome. – Brian M. Scott Sep 24 '12 at 20:21

If you have a language $L$ defined by grammar $$S \to a \\ S \to b$$ the language $L^*$ can be defined by $$S \to a \\ S \to b \\ S \to aS \\ S \to bS$$

-
Almost, but you also need to include a production to generate the empty string (which, of course, will always be in $L^*$). As you, I'm still waiting for definitions of Vn1, Vt, P1, and S1. – Rick Decker Sep 24 '12 at 19:43
@Rick: I have very little doubt that they are the set of non-terminals, the set of terminals, the set of productions, and the initial symbol, respectively. – Brian M. Scott Sep 24 '12 at 19:48
@Brian. That was my guess, as well. – Rick Decker Sep 24 '12 at 19:50
@Rick: W’ve seen the notation before, in exactly this form, though the poster was using a different account. – Brian M. Scott Sep 24 '12 at 19:51
@Brian. That being the case, Karolis' hint was pretty good (modulo the empty string). – Rick Decker Sep 24 '12 at 19:53