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?

  • 0
    Are Vn1, Vt, P1, S1 just weirdly named terminals or do they stand for something?2012-09-24
  • 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
    Is the null character in type 3 grammar?2012-09-24
  • 0
    @Mike: Yes: the type $3$ grammars are the [regular grammars](http://en.wikipedia.org/wiki/Regular_grammar), which allow null productions.2012-09-24
  • 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
    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.2012-09-24
  • 0
    @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.2012-09-24
  • 0
    @Brian. That was my guess, as well.2012-09-24
  • 0
    @Rick: W’ve seen the notation before, in exactly this form, though the poster was using a different account.2012-09-24
  • 0
    @Brian. That being the case, Karolis' hint was pretty good (modulo the empty string).2012-09-24
  • 0
    @BrianM.Scott I"m not the same user, I just copied the notation from him G1 = same thing. Is the null character in type 3 grammar?2012-09-24
  • 0
    @Mike: I didn’t mean to imply that you were the same person; I really wasn’t sure either way.2012-09-24