Theory of Computation MCQ with Answers

Theory of Computation MCQ with Answers

31) CFG can be recognized by a

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

Answer is:

I, III and IV

33) A given grammar is called ambiguous if

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

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

Answer is:

regular language

4
5
6
7
8
9
10