Home / Engineering / Theory of Computation MCQs / Page 12

# Theory of Computation MCQs | Page - 12

Dear candidates you will find MCQ questions of Theory of Computation here. Learn these questions and prepare yourself for coming examinations and interviews. You can check the right answer of any question by clicking on any option or by clicking view answer button.

## ```Q. 111) Following syntax-directed translation scheme is used with a shift reduction (bottom up) parser that perform the action in braces immediately after a reduction by the corresponding production A —>aB {print “(1)” A —> c {print “1”), B —>Ab {print *2”}. When parser is aaacbbb, then string printed```

(A) 0202021
(B) 1202020
(C) 1020202
(D) None of these

## `Q. 112) FSM can recognize`

(A) Any grammar
(B) Only CG
(C) Both (a) and ( b )
(D) Only regular grammar

## `Q. 113) Basic limitation of FSM is that it`

(A) Cannot remember arbitrary large amount of information
(B) Sometimes fails to recognize grammars that are regular
(C) Sometimes recognizes grammars are not regular
(D) None of these

(A) 1 and 2
(B) 1 and 4
(C) 2 and 3
(D) 2 and 4

## `Q. 115) If L and L¯ are recursively enumerable, then L is`

(A) Regular
(B) Context free
(C) Context sensitive
(D) Recursive

## `Q. 116) Which of the following problems is undecidable?`

(A) Membership problem for CFGs
(B) Ambiguity problem for CFGs.
(C) Finiteness problem for FSAs.
(D) Equivalence problem for FSAs.

## `Q. 117) Fred created a new automaton model which is a push down automaton but with two stacks and the added ability of having commands which do not read input tape but which can pop from one stack and push into the other.This new automaton can recognize (choose strongest result)`

(A) Context Free Language
(B) Context sensitive language
(C) Regular language
(D) Languages recognizable by Turing machine

(A) 1 and 4 only
(B) 1 and 3 only
(C) 2 only
(D) 3 only

## `Q. 119) Consider a string s over (0+1)*. The number of 0’s in s is denoted by no(s) and the number of 1’s in s is denoted by n1(s). The language that is not regular is`

(A) L = {s ε (0+1)* I for every prefix s’ of s, I no(s’)-n1(s’) I ≤ 2}
(B) L = {s ε (0+1)* I no(s) mod 7 = n1(s) mod 5 = 0}
(C) L = {s ε (0+1)* I no(s) is a 3 digit prime}
(D) L = {s ε (0+1)* I no(s)-n1(s) I ≤ 4

## `Q. 120) Which one of the following is true regarding FOTRAN?`

(A) It is a context free language
(B) It is a context sensitive language
(C) It is a regular language
(D) None of the above

Download our easy to use, user friendly Android App from Play Store. And learn MCQs with one click.