Theory of Computation (3160704) MCQs

MCQs of Context free grammar (CFG)

Showing 11 to 20 out of 36 Questions
1 2 3 4
11.
S → aSa|bSb|a|b; The language generated by the above grammar over the alphabet {a,b} is the set of
(a) All length palindrome
(b) Even length palindrome
(c) Odd length palindrome
(d) String starts and end with different character
Answer:

Option (c)

12.
There exists a Context free grammar such that: X→Xa is
(a) Left Recursive Grammar
(b) Non Recursive Grammar
(c) Right Recursive Grammar
(d) none of these
Answer:

Option (a)

13.
S→aSS→a is which grammar?
(a) Left Linear Grammar
(b) Right Linear Grammar
(c) Both of the mentioned
(d) None of the mentioned
Answer:

Option (b)

14.
Which of the following is the correct representation of grammar for the given regular expression? a(aUb)*b
(a) (1) S → aMb (2) M → e (3) M → aM (4) M → bM
(b) (1) S → aMb (2) M → e (3) M → aMb (4) M → bMa
(c) (1) S → aMb (2) M → Mab (3) M → aM (4) M → bM
(d) None of the mentioned
Answer:

Option (a)

15.
The context free grammar S → SS | 0S1 | 1S0 | ^  generates
(a) Unequal number of 0’s and 1’s
(b) Equal number of 0’s and 1’s
(c) Any number of 0’s followed by any number of 1’s
(d) None of these
Answer:

Option (b)

16.
CFG for balanced parenthesis
(a) S→ [] | {} | [s] | {s} | ^
(b) S→ [] | {}
(c) S→ [s] | {s}
(d) S→ [s] | {s} |[]
Answer:

Option (a)

17.
The language of {a, b} ends in a
(a) S→aS | bS
(b) S→aS | bS |b
(c) S→aS | bS |S
(d) S→aS | bS |a
Answer:

Option (d)

18.
The following production rules of a regular grammar generate a language L: S→ aS | bS | a | b The regular expression of L is
(a) a + b
(b) (a + b)(a + b)*
(c) (a + b)*
(d) (aa + bb) a*b*
Answer:

Option (b)

19.
Which of the following languages are context free language?
(a) L=aibi|i>=0
(b) L={wwr| w is a string and r represents reverse}
(c) Both of these
(d) None of the mentioned
Answer:

Option (a)

20.
The most suitable data structure used to represent the derivations is:
(a) Queue
(b) Tree
(c) Linked List
(d) Stack
Answer:

Option (b)

Showing 11 to 20 out of 36 Questions
1 2 3 4