3 3 votes The following grammar S$\rightarrow$SS|a|∈ can generate a*... which itself is a regular language but the grammar is neither right linear nor left linear... And we have studied that regular languages are always left or right linear.. Why is there such contradiction....? Theory of Computation theory-of-computation regular-language finite-automata + – Chetnawadhwa 3.4k views answer comment Share Follow Print 0 reply Please log in or register to add a comment.
Best answer 2 2 votes The above mentioned grammar is context free grammar which is a superset of regular grammar i.e. All regular languages are context free but all context free languages are not regular. Thus regular grammar can be expressed as cfg. Hope this help. Please drop a comment in case of a query. Thanks shantanu kaushik answered Jul 16, 2016 • selected Jul 17, 2016 by Chetnawadhwa shantanu kaushik comment Share Follow See all 17 Comments 17 17 Comments reply Tauhin Gangwar commented Jul 16, 2016 reply Follow flag kaushik is correct ....///@ chetna there is no contradiction....regular grammar is either left linear or linear is correct..but it doesn't mean that..there is only one grammar..for a language...there can be many grammars that can generate it...and all grammars need not 2 be regular...but there exist atleast one regular grammar 4 every regular language.. 0 0 replyShare sh!va commented Jul 16, 2016 reply Follow flag So the conclusion is : If a grammar is left or right linear, it is regular grammar.Otherwise it is not regular. Am I right? 0 0 replyShare Chetnawadhwa commented Jul 16, 2016 reply Follow flag @tauhin n shantanu.. Thanks for ur reply but.. I know that this is not regular grammar but i am asking dt finite automata can be there only for regular grammar right..? And this is not a regular grammar.. Its a cfg.. But we can draw a finite automata for this grammar.. Why.? 0 0 replyShare Chetnawadhwa commented Jul 16, 2016 reply Follow flag @tauhin n shantanu.. Thanks for ur reply but.. I know that this is not regular grammar but i am asking dt finite automata can be there only for regular grammar right..? And this is not a regular grammar.. Its a cfg.. But we can draw a finite automata for this grammar.. Why.? @shiva loyal Yes u r right.. In fact every right linear grammar can be converted into left linear n vice-versa... 0 0 replyShare shantanu kaushik commented Jul 17, 2016 reply Follow flag Yes, for a grammar to be regular it has to be either left or right linear and not a combination of both. 0 0 replyShare shantanu kaushik commented Jul 17, 2016 reply Follow flag @chetnawadhwa - Because CFG is a super set of regular grammar. You are right that finite automata can be given only for regular grammar and for the mentioned language the regular grammar is S-->aS/€. And you can give n number of cfg for the same language. Infact all the regular languages can be generated using regular grammar and using cfg as well. Hope this helps. Thanks 1 1 replyShare Tauhin Gangwar commented Jul 17, 2016 reply Follow flag @chetna plz draw the FA for this grammar...S------>SS|a|∈ how u will draw...let me know??? 0 0 replyShare Chetnawadhwa commented Jul 17, 2016 reply Follow flag @shantanu- u mean that whichever language can be defined using a finite automata..there definitely exists a regular grammar for it and n no of nonregular grammars can also exist.. But at least one reg grammar will b dre... Is dt so..? @tauhin-this grammar represents the language a*.. And we can draw a finite automata for it.. With only one state as initial n final with a loop on itself..!! 1 1 replyShare shantanu kaushik commented Jul 17, 2016 reply Follow flag exactly 0 0 replyShare Chetnawadhwa commented Jul 17, 2016 reply Follow flag @shantanu can u pl answer this ques S-->Sab|AB A-->aA|epsilon B-->bB|epsilon Does this grammar generate regular language..? Acc to me it is a regular lang.. Am i right? 0 0 replyShare Tauhin Gangwar commented Jul 17, 2016 i edited by Tauhin Gangwar Jul 17, 2016 reply Follow flag @chetna u said "-this grammar represents the language a*.. And we can draw a finite automata for it.. With only one state as initial n final with a loop on itself..!!" u cannot say like this.....use step by step...procedure..to convert regular grammar into dfa...and check the S-->SS|a|∈ can u draw dfa 4 this or not... "A language is regular iff there exist a regular grammar"...it doesn't mean all the grammar's that generates a language should be regular.... "A NON-REGULAR GRAMMAR CAN ALSO GENERATE REGULAR LANGUAGE" ....i hope u understand 0 0 replyShare Chetnawadhwa commented Jul 17, 2016 reply Follow flag @tauhin- thats what my question was.. Can non regular grammar also generate regular language..? When i was going step by step i was getting confused by the results as i was not craming rather trying to understand the concept behind that... Thank u so much for ur help.. 0 0 replyShare shantanu kaushik commented Jul 17, 2016 reply Follow flag This is my attempt to answer your question: 0 0 replyShare Tauhin Gangwar commented Jul 17, 2016 reply Follow flag ok chetna sorry u were trying 2 understand 0 0 replyShare Chetnawadhwa commented Jul 17, 2016 reply Follow flag @shantanu-I also followed d same approach but the only difference is the regular grammar which u got from the automata u drew... How did u get it?? .. Bcz the way i followed, m gettng wrong regular grammar...!! Plz tell 0 0 replyShare shantanu kaushik commented Jul 17, 2016 reply Follow flag Once you have successfully built the FA for it then it is all mechanical. I'll tell you how. Take the initial state of FA (A) as the Start state in regular grammar (S) and then write productions for each transition of initial state like S on 'a' goes to S (i.e. initial state A on 'a' goes to A) itself and S on 'b' goes to next state A (State B of FA). epsilon production is included as the initial state is final as well according to FA. Repeat this for all the states in FA to complete the RG. Please refer my answer in previous comment to co-relate to my statements here. P.S.-I know I couldn't explain it very clearly. Please observe carefully to find the solution. In my answer State A, B, C, D of FA correspond to variables S, A, B, C in grammar respectively Thanks. 0 0 replyShare Chetnawadhwa commented Jul 18, 2016 reply Follow flag @shantanu - thanks a lot for ur help.. variable names were different.. Thats why i was getting confused.. Thank you so much..!! 0 0 replyShare Please log in or register to add a comment.
