Register

ISRO-DEC2017-22

• recategorized by
3,421 views
4 votes
4 votes

Consider the grammar with productions

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

This grammar is 

  1. not context-free, not linear
  2. not context-free, linear
  3. context-free, not linear
  4. context-free, linear
• recategorized by
User Avatar

2 Answers

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

• selected by
User Avatar
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

 

User Avatar
Voting & Accepting an answer helps improve the community
Answer:
← PreviousNext →
← Previous in categoryNext in category →

Related questions

5 votes
5 votes
2 answers
1
gatecse asked Dec 17, 2017
1,214 views
ISRO-DEC2017-26
Which of the following are context-free? $A=\{a^n b^n\, a^mb^m\mid m,n\geq0\}$ $B=\{a^m b^n\, a^mb^n\mid m,n\geq0\}$ $C=\{a^mb^n\mid m\neq 2n,\,m,n\geq0\}$ A and B only A and C only B and C only C only
Which of the following are context-free?$A=\{a^n b^n\, a^mb^m\mid m,n\geq0\}$$B=\{a^m b^n\, a^mb^n\mid m,n\geq0\}$$C=\{a^mb^n\mid m\neq 2n,\,m,n\geq0\}$A and B only A and...
User Avatar
1 votes
1 votes
1 answer
2
gatecse asked Dec 17, 2017
1,038 views
ISRO-DEC2017-25
Let $L=\{a^p\mid p \text{ is a prime}\}.$ Then which of the following is true It is not accepted by a Turing Machine It is regular but not context-free It is context-free but not regular It is neither regular nor context-free ,but accepted by a Turing Machine
Let $L=\{a^p\mid p \text{ is a prime}\}.$ Then which of the following is trueIt is not accepted by a Turing MachineIt is regular but not context-freeIt is context-free b...
User Avatar
4 votes
4 votes
1 answer
3
gatecse asked Dec 17, 2017
1,326 views
ISRO-DEC2017-24
Let $L_1$ be regular language, $L_2$ be a deterministic context free language and $L_3$ a recursively enumerable language, but not recursive. Which one of the follewing statements is false ? $L_3\cap L_1$ is recursive $L_1\cap L_2\cap L_3$ is recursively enumerable $L_1\cup L_2$ is context free $L_1\cap L_2$ is context free
Let $L_1$ be regular language, $L_2$ be a deterministic context free language and $L_3$a recursively enumerable language, but not recursive. Which one of the follewing st...
User Avatar
3 votes
3 votes
2 answers
4
gatecse asked Dec 17, 2017
2,020 views
ISRO-DEC2017-23
Identify the language generated by the following grammar $S\rightarrow AB\\ A\rightarrow aAb\mid \varepsilon\\ B\rightarrow bB\mid b$ $\{a^m b^n\mid n\geq m,m>0\}$ $\{a^m b^n\mid n\geq m,m\geq0\}$ $\{a^m b^n\mid n> m,m>0\}$ $\{a^m b^m\mid n> m,m\geq0\}$
Identify the language generated by the following grammar$S\rightarrow AB\\ A\rightarrow aAb\mid \varepsilon\\ B\rightarrow bB\mid b$$\{a^m b^n\mid n\geq m,m>0\}$ $\{a^m b...
User Avatar
Link Copied!