0
$\begingroup$

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

L(G1) =  

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?

  • 1
    they are the set of non-terminals, the set of terminals, the set of productions, and the initial symbol, respectively.2012-09-24

2 Answers 2

2

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.

  • 0
    @Mike: You’re very welcome.2012-09-24
1

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$

  • 0
    @Mike: I didn’t mean to imply that you were the same person; I really wasn’t sure either way.2012-09-24