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

Theory of Computation MCQ with Answers

For more MCQ's Click Here

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

35) The grammars G = ( { s }, { 0, 1 }, p , s) where p = (s —> 0S1, S —> OS, S —> S1, S —>0} is a

recursively enumerable language

regular language

context-sensitive language

context-free language

Answer is:

regular language

Theory of Computation MCQ with Answers

For more MCQ's Click Here

31) CFG can be recognized by a

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

Theory of Computation MCQ with Answers

Related Theory of Computation MCQ with Answers

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

35) The grammars G = ( { s }, { 0, 1 }, p , s) where p = (s —> 0S1, S —> OS, S —> S1, S —>0} 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