Computation Theory MCQs
Computation Theory MCQs
Our experts have gathered these Computation Theory MCQs through research, and we hope that you will be able to see how much knowledge base you have for the subject of Computation Theory by answering these multiple-choice questions.
Get started now by scrolling down!
1: For the language {ap I P is a prime}, the statement which hold true is
A. It is not regular but context free
B. It is neither regular nor context free, but accepted by a turing machine
C. It is not accepted by turing machine
D. It is regular but not context free
2: The language described by the regular expression (0+1)*0(0+1)*0(0+1)* over the alphabet {0 1} is the set of:
A. All strings containing the substring 00
B. All strings containing at least two 0’s
C. All strings that begin and end with either 0’s or 1’s
D. All strings containing at least two 1’s
3: Which one of the following is applicable for context free languages?
A. These are closed under complement, Kleene closure
B. These are closed under union, Kleene closure
C. These are closed under intersection, complement
D. These are closed under union, intersection
4: The true regular expression is:
A. R(*) = r*
B. (r*s*)* = (r+s)*
C. R*s* = r* + s*
D. (r+s)* = r* + s*
5: Out of the three decision problems P1, P2 and P3, P1 is decidable and P2 is undecidable. The statement that holds true is:
A. P3 is undecidable if P1 is reducible to P3
B. P3 is undecidable if P2 is reducible to P3
C. P3 is decidable if P3 is reducible to compliment of P2
D. P3 is decidable if P1 is reducible to P3
6: Consider the language L = {W I W ∈ {0, 1}*, where 0’s and 1’s in W are divisible by 3 and 5 respectively. The minimum state deterministic finite automaton accepting the language L has:
A. 15 states
B. 10 states
C. 5 states
D. 20 states
7: The set that can be recognized by a deterministic finite state automaton is:
A. The set of binary string in which the number of 0’s is same as the number of 1’s
B. The set {1, 101, 11011, 1110111, …….}
C. 1, 2, 4, 8……2n ….. written in binary
D. 1, 2, 4, 8……2n ….. written in unary
8: We have an undirected graph G(V, E) with two problems given below: α – Does G have an independent set of size IVI – 4? β – Does G have an independent set of size 5? The statement that holds true is:
A. Both α and β are NP-complete
B. α is NP-complete and β is in P
C. α is in P and β is NP-complete
D. Both α and β are in P
9: 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 no(s)-n1(s) I ≤ 4
B. L = {s ∈ (0+1)* I no(s) mod 7 = n1(s) mod 5 = 0}
C. L = {s ∈ (0+1)* I for every prefix s’ of s, I no(s’)-n1(s’) I ≤ 2}
D. L = {s ∈ (0+1)* I no(s) is a 3 digit prime}
10: Which one of the following is true for this automaton?
A. B*ab*ab*
B. B*a(a+b)*
C. B*ab*ab*ab*
D. (a+b)*
11: 3-SAT and 2-SAT problems are:
A. Both in P
B. NP-complete and in P respectively
C. Both NP-complete
D. Undecidable and NP-complete
12: From the options given below, the pair having different expressive power is:
A. Single tape turning machine and multi tape turning machine
B. Deterministic single tape turning machine and Non-Deterministic single tape turning machine
C. Deterministic Push Down Automata (DPDA) and Non-deterministic Push Down Automata (NPDA)
D. Deterministic Finite Automata (DFA) and Non-deterministic Finite Automata(NFA)
13: Which one of the following statement is true?
A. The union of two context free languages is context free
B. The complement of a context free language is context free
C. The intersection of two context free languages is context free
D. A context free language can always be accepted by a deterministic push down automaton
14: The problem that is undecidable:
A. Membership problem for CFG’s
B. Equivalence problem for FSA’s
C. Finiteness problem for FSA’s
D. Ambiguity problem for CFG’s
15: Let n be the length of a character string. How many substrings (of all lengths inclusive) can be formed from n?
A. (n (n+1)/2) + 1
B. N
C. N-1
D. N(n-1)/2
16: The last two symbols of L which is the set of all binary strings are same. In the minimum state deterministic finite state automaton, which is accepting L _____, states are present.
A. 4
B. 8
C. 5
D. 6
17: We have decision problems P1 and P2 as described below: P1: Does a given finite state machine accept a given string? P2: Does a given context-free grammar generate an infinite number of strings? The statement that holds true for P1 and P2 is:
A. Neither P1 nor P2 are decidable
B. Only P1 is decidable
C. Both P1 and P2 are decidable
D. Only P2 is decidable
18: Which one of the following statement is true for the C language?
A. It is context-free language
B. It is a regular language
C. It is parsable fully only by a turing machine
D. It is context-sensitive language
19: We have two statements S1 and S2 whose definition are as follows: S1 – {02n In ≥ I} is a regular language. S2 – {0m 1n 0 1m+n Im=1 and n≥1I is a regular language. Which one of the following statements is correct?
A. Both S1 and S2 are correct
B. Only S2 is correct
C. Neither S1 nor S2 is correct
D. Only S1 is correct
20: The problem, which is not NP-hard, is:
A. The 0/1 Knapsack problem
B. The graph colouring problem
C. Hamiltonian circuit problem
D. Finding bi-connected problem of a graph
List of Computation Theory MCQ...
Available in:
Computation Theory MCQs
