ISRO-DEC2017-22

Question

Consider the grammar with productions

$S\rightarrow aSb\mid SS \mid \varepsilon$

This grammar is 

• A. not context-free, not linear
• B. not context-free, linear
• C. context-free, not linear
• D. context-free, linear

Answer 1

• 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

Comments

can u tell language generated by this cfg @sh1va

---

@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.

---

 Jaspreet Singh 4 you are right.

S--->aSb is linear grammar but not left and right linear grammar .

---

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".

Answer 2

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