0 0 votes L={w∣na(w)=nb(w)}L={w∣na(w)=nb(w)} is deterministic context free language, but not linear. HOW THIS Language is not linear S-->aA/bB A-->Sb/b B-->Sa/a i think this grammar is correct for this language? how this grammar is not linear? Theory of Computation + – pream sagar 1.4k views answer comment Share Follow Print See all 7 Comments 7 7 Comments reply Satbir commented Dec 19, 2018 reply Follow flag your grammar is not accepting Є ....which should have been accepted in the language. 0 0 replyShare pream sagar commented Dec 19, 2018 reply Follow flag if i add another production S-->Є then? 0 0 replyShare kumar.dilip commented Dec 19, 2018 reply Follow flag https://gateoverflow.in/114283/ugcnet-dec2016-iii-61 0 0 replyShare pream sagar commented Dec 19, 2018 reply Follow flag they did not explain the answer only give reference of book. so please see my grammar i know this statement from peter linz book then definitely true but i want to know why this grammar i wrong? 0 0 replyShare shreyansh jain commented Dec 19, 2018 i edited by shreyansh jain Dec 19, 2018 reply Follow flag @pream sagar Grammar is incomplete actually, try to generate the strings starting and ending with same symbol and still having equal number of a's and b's something like $abba$. Your grammar can only derive strings of the form: $a^n(b^na^n)b^n$ and $b^n(a^nb^n)a^n$ 0 0 replyShare pream sagar commented Dec 19, 2018 reply Follow flag i got it thank u 0 0 replyShare Ram Swaroop commented Dec 19, 2018 reply Follow flag https://en.m.wikipedia.org/wiki/Linear_grammar 0 0 replyShare Please log in or register to add a comment.
