0 votes 0 votes Regular grammars can only describe regular languages, why reverse is not true .What should be the most appropriate Reason ? Explain with in few Lines .If possible give an exp too. Theory of Computation theory-of-computation regular-language + – shekhar chauhan asked Jun 6, 2016 • retagged Jun 4, 2017 by Arjun shekhar chauhan 2.6k views answer comment Share Follow See all 0 reply Please log in or register to add a comment.
Best answer 3 votes 3 votes The language generated by any regular grammar will be regular - same as saying regular grammar can only describe regular languages. But for regular language we can generate it by non-regular grammar also. For example $a^*b^*$ can be generated by a non-regular grammar S → aA A → Sb | ε S → ε This makes the reverse statement false. srestha answered Jun 6, 2016 • selected Jun 7, 2016 by Arjun srestha comment Share Follow See all 14 Comments See all 14 14 Comments reply ManojK commented Jun 7, 2016 reply Follow Share it should be true for both . 0 votes 0 votes Praveen Saini commented Jun 7, 2016 reply Follow Share Regular grammar will be either right linear or left linear, for which we can design corresponding DFA, i.e, resulting is regular language. Regular languages can be represented by regular grammar, cfg , csg , as per chomsky hierarchy. 0 votes 0 votes shekhar chauhan commented Jun 7, 2016 reply Follow Share a/c to my why argument how can we determine a regular language from the grammar other then regular grammar.this is what i meant to ask but in your explanation you are talking about again LLG and RLG .But i don't want to derive a regular language from regular grammar here this is what exactly the question is . 0 votes 0 votes Arjun commented Jun 7, 2016 reply Follow Share @srestha Second part is fine but for first part you are repeating the same mistake. Say to prove $A \implies B$, it is not enough to say that when one instance of A is true B is also true. We have to prove for EVERY such instances. @shekhar So what exactly is the question? ;) 0 votes 0 votes shekhar chauhan commented Jun 7, 2016 reply Follow Share sir problem is Regular grammars can only describe regular languages .i am sure about this statement if a grammar is regular then definitly we are going to get regular language but Question is why reverse of this is not true. (what i assume is there can be some regular language which can't be generated by regular grammar ) if i am wrong please correct it .now why is this true.if a lang is regular then it should be generated by regular grammar. 0 votes 0 votes Arjun commented Jun 7, 2016 reply Follow Share okay. Regular grammars can only describe regular languages This means if a grammar is regular, its language is regular. Reverse will be, if a language is regular then the grammar which generated it is regular. To prove this statement we should give a grammar which is not regular but generating a regular language- which is what is given by @srestha 0 votes 0 votes shekhar chauhan commented Jun 7, 2016 reply Follow Share I got it one more question does this statement make sense there can be some regular language which can't be generated by regular grammar 0 votes 0 votes Arjun commented Jun 7, 2016 reply Follow Share It makes sense, but is false. There is no regular language which cannot be generated by a regular grammar. 0 votes 0 votes shekhar chauhan commented Jun 7, 2016 reply Follow Share no no this is not i meant to ask ,i mean is there any regular language which can be generated by grammar which is not regular grammar(it may be CFG or CSG or any other grammar).This is i want to ask. 0 votes 0 votes srestha commented Jun 7, 2016 reply Follow Share @Arjun sir yes I have done mistake in 1st statement means as Praveen sir told if Regular grammar will be both right linear and left linear, resulting cannot be a regular language. That case I also have to consider . So 1st statement is also false 0 votes 0 votes Arjun commented Jun 7, 2016 reply Follow Share @shekhar have you completed mathematical logic part from Rosen? What you asked is exactly the reverse case of this question. @srestha Are you saying that the language generated by a regular grammar can be non-regular? 0 votes 0 votes srestha commented Jun 7, 2016 reply Follow Share yes if it is aibi then it is CFL , which is not regular , like, it can be generate like S->aSb rt? 0 votes 0 votes Arjun commented Jun 7, 2016 reply Follow Share that grammar is not regular grammar rt? 0 votes 0 votes srestha commented Jun 7, 2016 reply Follow Share yes not CFL actually , but is not regular 0 votes 0 votes Please log in or register to add a comment.