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

share|improve this question
    
Are Vn1, Vt, P1, S1 just weirdly named terminals or do they stand for something? –  Karolis Juodelė Sep 24 '12 at 19:34
1  
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

2 Answers 2

up vote 2 down vote accepted

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.

share|improve this answer
    
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$$

share|improve this answer
    
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

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.