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
View Answer Discuss Share

Q. 112) FSM can recognize

(A) Any grammar
(B) Only CG
(C) Both (a) and ( b )
(D) Only regular grammar
View Answer Discuss Share

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
View Answer Discuss Share

Q. 114) Which of the following are decidable?
1) Whether the intersection of two regular language is infinite.
2) Whether a given context free language is regular.
3) Whether two push down automata accept the same language.
4) Whether a given grammar is context free.

(A) 1 and 2
(B) 1 and 4
(C) 2 and 3
(D) 2 and 4
View Answer Discuss Share

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

(A) Regular
(B) Context free
(C) Context sensitive
(D) Recursive
View Answer Discuss Share

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.
View Answer Discuss Share

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
View Answer Discuss Share

Q. 118) Which of the following statements is/are FALSE?
(1) For every non-deterministic Turing machine, there exists an equivalent deterministic Turing machine.
(2) Turing recognizable languages are closed under union and complementation.
(3) Turing decidable languages are closed under intersection and complementation
(4) Turing recognizable languages are closed under union and intersection.

(A) 1 and 4 only
(B) 1 and 3 only
(C) 2 only
(D) 3 only
View Answer Discuss Share

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
View Answer Discuss Share

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
View Answer Discuss Share