MCQs of Context free grammar (CFG) (Theory of Computation - 3160704)

Theory of Computation (3160704) MCQs

MCQs of Context free grammar (CFG)

Showing 21 to 30 out of 36 Questions

21.

Which among the following is the root of the parse tree?

(a)	Production P
(b)	Nonterminal V
(c)	Terminal T
(d)	Starting symbol S

22.

__________ is the graphical representation of a grammar.

(a)	Binary tree
(b)	Red black tree
(c)	Parse tree
(d)	None of the mentioned

23.

Which of the following derivations does a top-down parser use while parsing an input string? The input is assumed to be scanned in left to right order

(a)	Leftmost derivation
(b)	Leftmost derivation traced out in reverse
(c)	Rightmost derivation
(d)	Rightmost derivation traced out in reverse

24.

A context free language is called ambiguous if

(a)	It has two or more leftmost derivations for some terminal string
(b)	It has two or more leftmost derivations for some terminal string
(c)	Both A and B
(d)	None of these

25.

CFGs are more powerful than

(a)	DFA
(b)	Mealy Machine
(c)	NFA
(d)	All of the mentioned

26.

Every grammar in Chomsky Normal Form is:

(a)	Regular
(b)	Context free
(c)	Context sensitive
(d)	Unrestricted

27.

While converting the context free grammar into chomsky normal form, which of the following is necessary

(a)	Elimination of null production
(b)	Elimination of unit production
(c)	Converting given grammar in Chomsky normal form
(d)	All of these

28.

Which of the following grammars are in Chomsky Normal Form:

(a)	S $\to$ AB\|BC\|CD A->0 B $\to$ 1 C $\to$ 2 D $\to$ 3
(b)	S $\to$ AB S $\to$ BCA\|0\|1\|2\|3
(c)	S $\to$ ABa A $\to$ aab B $\to$ Ac
(d)	All of the mentioned

29.

In conversion from CFG to CNF, the number of nonterminal to be introduced for the terminals are:

S \to A B a A \to a a b B \to A c

(a)	2
(b)	3
(c)	4
(d)	1

30.

The variable which produces

\in

is called:

(a)	Empty variable
(b)	Nullable variable
(c)	Terminal
(d)	All of the mentioned

Showing 21 to 30 out of 36 Questions