1 votes 1 votes What type of grammar is this most accurately described as? S-> b/ aD D-> a/ aDD A. A regular grammar B. CFG C. CSG D. Type-0 Pranav Kapur asked Mar 24, 2016 Pranav Kapur 4.9k views answer comment Share Follow See all 0 reply Please log in or register to add a comment.
Best answer 7 votes 7 votes option B s->b/aD right linear grammar D->a/aDD context free grammar so altogether its CFG Bhagirathi answered Mar 24, 2016 • selected Mar 27, 2016 by Praveen Saini Bhagirathi comment Share Follow See all 17 Comments See all 17 17 Comments reply srestha commented Mar 25, 2016 reply Follow Share grammar could be b or (aa)*. right? then it will be regular grammar. right? 0 votes 0 votes vamsi2376 commented Mar 26, 2016 reply Follow Share No.... Bhagirathi is correct. s->b/aD is Type 3 D->a/aDD is Type 2 We consider highest form of the grammer. So it is Type 2 (CFG). 0 votes 0 votes srestha commented Mar 26, 2016 reply Follow Share ok But see D->a/aDD is a(aa)* So, it is type3 grammar 0 votes 0 votes Praveen Saini commented Mar 27, 2016 reply Follow Share Do not confuse between grammar and language. 1 votes 1 votes srestha commented Mar 27, 2016 reply Follow Share D->a/aDD is a right linear grammar a(aa)* is a regular language right? 0 votes 0 votes Praveen Saini commented Mar 27, 2016 reply Follow Share D->a/aDD is a right linear grammar --> NOa(aa)* is a regular language ---> Yes. 0 votes 0 votes srestha commented Mar 27, 2016 reply Follow Share ok right linear A->αβ where α=1,β=0/1 then D->a/aDD only recursive?? 0 votes 0 votes Praveen Saini commented Mar 27, 2016 reply Follow Share Regular Grammar: One Nonterminal -> only terminals or one Nonterminal -> having only one NonTerminal at left/right with/without terminals Context-free Grammar: One Nonterminal -> any combination of Terminals/Nonterminals 4 votes 4 votes srestha commented Mar 27, 2016 reply Follow Share ok got it It is a s grammar (simple) ,which is LL(0) and context free 0 votes 0 votes viv696 commented Mar 31, 2016 reply Follow Share sir , S->aS | Sb| e is above grammar regular>? 0 votes 0 votes Praveen Saini commented Mar 31, 2016 reply Follow Share No it is not@viv , afaik, regular grammar should be either left linear or right linear only. 0 votes 0 votes vamsi2376 commented Mar 31, 2016 reply Follow Share No its not regular... Bcoz the language generated by the given production rule is ae, eb, aeb, aaeb, aebb, aaebb,........ We can't construct a finite automata for this language... So it is not regular.... 0 votes 0 votes viv696 commented Apr 1, 2016 reply Follow Share @vamsi :you have got it wrong. S->Sb|aS|e generates language L={ae, eb, aeb, aaeb, aebb, aaebb,........ ,ae,aae,aaae,aaaaae.....,eb,ebb,ebbbb,ebbbb........aaaaebb,aaebbb,aebbb,....} in general grammar generates language whose regular expression is ( a*eb* ) if regular expression exists then the language is regular. a regular grammar exists for every regular language. now the question was is S->Sb|aS|e a regular grammar? https://en.wikipedia.org/wiki/Linear_grammar 0 votes 0 votes Praveen Saini commented Apr 1, 2016 reply Follow Share $\epsilon$ 0 votes 0 votes vamsi2376 commented Apr 1, 2016 reply Follow Share Is it??? Then give me a FA for this... 0 votes 0 votes vamsi2376 commented Apr 1, 2016 reply Follow Share Every grammer is either is in either left linear or right linear form. But S->aS | Sb| e is neither left-linear nor right-linear and therefore is not regular. This is a linear grammer. 0 votes 0 votes swagnikd commented Apr 13, 2016 reply Follow Share S->b/aD is also regular grammar right? Since it is entirely right linear ? 0 votes 0 votes Please log in or register to add a comment.