Theory Of Computation Unit 4 Set 1
On This Page
This set of Theory of Computation Multiple Choice Questions & Answers (MCQs) focuses on Theory Of Computation Unit 4 Set 1
Q1 | If r1 = (aa + bb) and r2 = (a + b) then the language (aa + bb)(a + b) will be generated by Select correct option:
- (r1)(r2)
- (r1 + r2)
- (r2)(r1)
- (r1)
Q2 | Which of the following will be used for text searching application-?
- NFA
- DFA
- PDA
- None of these
Q3 | Context free grammar is used for-
- Lexical analyzer
- Document type definition (DTD)
- Text pattern searching
- Both a & c
Q4 | The set strings of 0's and 1's with atmost one pair consecutive one's-
- (0+1)*(01)(10)(0+1)*
- (0+1)*(01)*(10)(0+1)*
- (0+1)*(01)(10)*(0+1)*
- (0+!)(01)*(10)*(0+1)
Q5 | The problem 3-SAT and 2-SAT are
- Both in P
- Both NP complete
- NP-complete and in P respectively
- Undecidable and NP-complete respectively
Q6 | Which of the following instances of the post correspondence problem has a viable sequence (a solution)?
- {(b, bb), (bb, bab), (bab, abb), (abb, babb)}
- {(ab, aba), (baa, aa), (aba, baa)}
- {(ab, abb), (ba, aaa), (aa, a)}
- none of the above
Q7 | Let FHAM be the problem of finding a Hamiltonian cycle in a graph G and DHAM be the problem of determining if a Hamiltonial cycle exists in a graph. Which one of the following is TRUE?
- Both FHAM and DHAM are NP-hard
- FHAM is NP hard, but DHAM is not
- DHAM is NP hard, but FHAM is not
- Neither FHAM nor DHAM is NP hard
Q8 | Consider three problems P1, P2 and P3. It is known that P1 has polynomial time solution and P2 is NP-complete and P3 is in NP. Which one of the following is true.
- P3 has polynomial time solution if P1 is polynomial time reducible to P3
- P3 is NP complete if P3 is polynomial time reducible to P2
- P3 is NP complete if P2 is reducible to P3
- P3 has polynomial time complexity and P3 is reducible to P2
Q9 | Which one of the following is the strongest correct statement about a finite language Lover a finite alphabet Σ?
- L is undecidable
- L is recursive
- L is a CSL
- L is a regular set
Q10 | Which one of the following is not decidable?
- given a Turing machine M, a string s, and an integer k, M accepts s with k steps
- equivalence of two given Turing machines
- language accepted by a given DFSA is nonempty
- language generated by a CFG is nonempty
Q11 | Which of the following statements are TRUE?(1) The problem of determining whether there exists a cycle in an undirected graph is in P.(2) The problem of determining whether there exists a cycle in an undirected graph is in NP.(3) If a problem A is NP-Complete, there exists a non-deterministic polynomial time algorithm to solve A.
- 1, 2 and 3
- 1 and 2 only
- 2 and 3 only
- 1 and 3 only
Q12 | Consider a graph G = (V, E) where I V I is divisible by 3. The problem of finding a Hamiltonian cycle in a graph is denoted by SHAM3 and the problem of determining if a Hamiltonian cycle exits in such graph is denoted by DHAM3. The option, which holds true, is
- Only DHAM3 is NP-hard
- Only SHAM3 is NP-hard
- Both SHAM3 and DHAM3 are NP-hard
- Neither SHAM3 nor DHAM3 is NP-hard
Q13 | Which of the following statement is false for a turing machine?
- There exists an equivalent deterministic turing machine for every nondeterministic turing machine
- Turing decidable languages are closed under intersection and complementation
- Turing recognizable languages are closed under union and intersection
- Turing recognizable languages are closed under union and complementation
Q14 | Two persons X and Y have been asked to show that a certain problem p is NP-complete. X shows a polynomial time reduction from the 3-SAT problem to p and Y shows a polynomial time reduction from p to 3-SAT. From these reduction it can be inferred that
- P is NP-complete
- P is NP-hard but not NP-complete
- P is in NP but not NP-complete
- P is neither NP-hard nor in NP
Q15 | 3-SAT and 2-SAT problems are
- NP-complete and in P respectively
- Undecidable and NP-complete
- Both NP-complete
- Both in P
Q16 | Let n be the positive integer constant and L be the language with alphabet {a}. To recognize L the minimum number of states required in a DFA will be
- 2k + 1
- k + 1
- 2n + 1
- n + 1
Q17 | Consider a stack, which is limited to 10 items. The language accepted by a push- down automaton in such stack is best described as
- Regular
- Deterministic context free
- Context free
- Recursive
Q18 | State table of an FSM is given below. There are two states A And B, one input and one output. Let the initial state be A = 0 and B = 0. To take the machine to the state A = 0 and B = 1 with output = 1 the minimum length of input string required will be
- 2
- 7
- 4
- 3
Q19 | Out of the three decision problems P1, P2 and P3, P1 is decidable and P2 is undecidable. The statement that holds true is
- P3 is decidable if P3 is reducible to compliment of P2
- P3 is decidable if P1 is reducible to P3
- P3 is undecidable if P1 is reducible to P3
- P3 is undecidable if P2 is reducible to P3
Q20 | The set which is not countable if we have ∑ = {a, b}, is
- Set of all languages over ∑ accepted by turing machine
- Set of all regular languages over ∑
- Set of all strings over ∑
- Set of all languages over ∑
Q21 | How many states are present in the minimum state finite automaton that recognizes the language represented by the regular expression (0+1)(0+1)…..N times?
- n+1
- n+2
- n
- 2n
Q22 | Consider the state table of a finite state machine that has input x and a single output z. The shortest input sequence to reach the final state C if the initial state is unknown is
- 10
- 01
- 101
- 110
Q23 | The set that can be recognized by a deterministic finite state automaton is
- The set {1, 101, 11011, 1110111, …….}
- The set of binary string in which the number of 0’s is same as the number of1’s
- 1, 2, 4, 8……2n ….. written in binary
- 1, 2, 4, 8……2n ….. written in unary