4 votes 4 votes Consider the grammar with productions $S\rightarrow aSb\mid SS \mid \varepsilon$ This grammar is not context-free, not linear not context-free, linear context-free, not linear context-free, linear Theory of Computation isrodec2017 + – gatecse asked Dec 17, 2017 • recategorized Feb 11, 2018 by srestha gatecse 3.4k views answer comment Share Follow See all 0 reply Please log in or register to add a comment.
Best answer 9 votes 9 votes In linear grammar All non terminals should be only in left side (Left linear) or right side (Right linear) In S→aSb, the non terminal S appears in middle. It is not linear Context free grammars have rules of the form A → w where A is a non-terminal, and w is a string (potentially empty) of terminals and non-terminals. In CFG non terminal can appear (in left, right or in between of RHS). Given grammar is context free Answer is C sh!va answered Jan 11, 2018 • selected Apr 20, 2018 by srestha sh!va comment Share Follow See all 4 Comments See all 4 4 Comments reply rio commented Mar 25, 2018 reply Follow Share can u tell language generated by this cfg @sh1va 0 votes 0 votes Jaspreet Singh 4 commented Apr 8, 2018 reply Follow Share @sh!va I think Your answer is correct but your explanation about the linear grammar is wrong. According to Wikipedia, Linear grammar is a context-free grammar that has at most one non-terminal on the right-hand side of each of its production. This production S -> aSb has no problem but S -> SS is not a linear production as in the right-hand side of the production there are two non-terminals. On the other hand, context-free grammar doesn't have such issues. The right-hand side of the production could have any number of terminals and non-terminals but left-hand side must contain only one non-terminal. If you find anything wrong, please correct it. 2 votes 2 votes abhishekmehta4u commented Apr 8, 2018 reply Follow Share Jaspreet Singh 4 you are right. S--->aSb is linear grammar but not left and right linear grammar . 0 votes 0 votes Mr.OOPs commented Apr 13, 2018 reply Follow Share also addition to that "To the right side Atmost one non-terminal must be either LEFTMOST or RIGHTMOST to show the linearity of the grammar(it means we have the conversion Algo proposed to Convert RLG to LLG and Vice versa". 0 votes 0 votes Please log in or register to add a comment.
3 votes 3 votes A linear grammar is a context-free grammar that has at most one non-terminal / variable in the right hand side of each of its productions. (Having only λ or ɛ in the RHS also counts). Here in question S->SS has more then one non-terminal, so its not linear. As there is no problem with context grammar ref:https://www.quora.com/What-is-the-difference-between-regular-grammar-and-linear-grammar-in-automata Swami patil answered Dec 6, 2018 Swami patil comment Share Follow See all 0 reply Please log in or register to add a comment.