30) In a context-free grammar

ε can't be the right hand side of any production

terminal symbols can't be present in the left hand side of any production

number of grammar symbols in the left hand side is not greater than the number of grammar symbols in the right hand side

all of these

Answer is:

all of these

Theory of Computation MCQ with Answers

For more MCQ's Click Here

31) CFG can be recognized by a

push-down automata

2-way linear bounded automata

both 1) push-down automata and 2) 2-way linear bounded automata

none of these

Answer is:

both 1) push-down automata and 2) 2-way linear bounded automata

32) Which of the following statements are true?
I. The set of all odd integers is a monoid under multiplication.
II. The set of all complex number is a group under multiplication
III. The set of all integers under the operation * given by a * b = a+b-ab is a monoid
IV. Zs under symmetric difference defined by
AB = (A-B) ∪(B-A) is an abelian group

I and II

I, III and IV

I, II and III

I, II and IV

Answer is:

I, III and IV

33) A given grammar is called ambiguous if

two or more productions have the same non-terminal on the left hand side

a derivation tree has more than one associated sentence

there is a sentence with more than one derivation tree corresponding to it

brackets are not present in the grammar

Answer is:

there is a sentence with more than one derivation tree corresponding to it

34) Let L be a language recognizable by a finite automaton. The language
REVERSE (L) = {w such that w is the reverse of v where v ∈L } is a

regular language

context-free language

context-sensitive language

recursively enumerable language

Answer is:

regular language

Theory of Computation MCQ with Answers

For more MCQ's Click Here

30) In a context-free grammar

all of these

Theory of Computation MCQ with Answers

Related Theory of Computation MCQ with Answers

31) CFG can be recognized by a

both 1) push-down automata and 2) 2-way linear bounded automata

I, III and IV

33) A given grammar is called ambiguous if

there is a sentence with more than one derivation tree corresponding to it

34) Let L be a language recognizable by a finite automaton. The language REVERSE (L) = {w such that w is the reverse of v where v ∈L } is a

regular language

Theory of Computation MCQ with Answers

34) Let L be a language recognizable by a finite automaton. The language
REVERSE (L) = {w such that w is the reverse of v where v ∈L } is a