Theory Of Computation Unit 3 Set 2
On This Page
This set of Theory of Computation Multiple Choice Questions & Answers (MCQs) focuses on Theory Of Computation Unit 3 Set 2
Q1 | The regular expression have all strings in which any number of 0’s is followed by any number of 1’s followed by any number of 2’s is :
- (0+1+2)*
- 0*1*2*
- 0* + 1 + 2
- (0+1)*2*
Q2 | Suppose that a problem A is known to have a polynomial-time verificationalgorithm. Which of the following statements can be deduced.
- A is in NP.
- A is in NP but not P
- A is in both NP and P.
- A is NP-complete.
Q3 | Which of the following assertions about Turing Machines is true? Blank symbol(s) may occur in the input. At any stage of a computation, there are only finitely many non-blank Symbols on the tape.
- Assertions (a) and (b) are both true.
- Neither (a) nor (b) is true.
- Both False
- None of above
Q4 | A PC not connected to a network is equivalent to
- A Deterministic Finite-State Automaton,
- A Turing Machine,
- A Push-Down Automaton,
- None of the above.
Q5 | Recursively enumerable languages are not closed under:
- Union
- Intersection
- Complementation
- Concatenation
Q6 | Let L1 be a recursive language, and let L2 be a recursively enumerable but not a recursive language. Which one of the following is TRUE?
- (L1)’ is recursive and (L2)’ is recursively enumerable
- (L1)’ is recursive and (L2)’ is not recursively enumerable
- (L1)’ and (L2)’ are recursively enumerable
- (L1)’ is recursively enumerable and (L2)’ is recursive
Q7 | Let S be an NP-complete problem, Q and R be two other problems not known to be in NP. Q is polynomial-time reducible to S and S is polynomial-time reducible to R. Which one of the following statements is true?
- R is NP-complete
- R is NP-hard
- Q is NP-complete
- Q is NP-hard
Q8 | For s Є (0+1)* let d(s) denote the decimal value of s(e.g.d(101)) = 5 Let L = {s Є (0+1)* d(s) mod 5=2 and d(s) mod 7 != 4} Which one of the following statements is true?
- L is recursively enumerable, but not recursive
- L is recursive, but not context-free
- L is context-free, but not regular
- L is regular
Q9 | A FSM can be considered, having finite tape length without rewinding capability and unidirectional tape movement
- Turing machine
- Pushdown automata
- Context free languages
- Regular languages
Q10 | Which of the following statement is true?
- All languages can be generated by CFG
- The number of symbols necessary to simulate a Turing Machine(TM) with m symbols and n states is mn.
- Any regular languages have an equivalent CFG.
- The class of CFG is not closed under union.
Q11 | Recursively enumerable languages are not closed under
- Complementation
- Union
- Intersection
- None of the above
Q12 | The following CFG is inS → aBBB → bAAA → aB → b
- Chomsky normal form but not strong Chomsky normal form
- Weak Chomsky normal form but not Chomsky normal form
- Strong Chomsky normal form
- Greibach normal form
Q13 | The languages -------------- are the examples of non regular languages.
- PALINDROME and PRIME
- PALINDROME and EVEN-EVEN
- EVEN-EVEN and PRIME
- FACTORIAL and SQURE
Q14 | Let L be any infinite regular language, defined over an alphabet Σ then there exist three strings x, y and z belonging to Σ such that all the strings of the form XY^ n Z for n=1,2,3, … are the words in L called
- Complement of L
- Pumping Lemma
- Kleene’s theorem
- None in given
Q15 | Languages are proved to be regular or non regular using pumping lemma.
- True
- False
- Not always true
- can’t say anything
Q16 | ___________ states are called the halt states.
- ACCEPT and REJECT
- ACCEPT and READ
- ACCEPT AND START
- ACCEPT AND WRITE
Q17 | The part of an FA, where the input string is placed before it is run, is called _______
- State
- Transition
- Input Tape
- Output Tape
Q18 | The PDA is called non-deterministic PDA when there are more than one out going edges from……… state
- START or READ
- POP or REJECT
- READ or POP
- PUSH or POP
Q19 | If an effectively solvable problem has answered in yes or no, then thissolution is called
- Decision procedure
- Decision method
- Decision problem
- Decision making
Q20 | The symbols that can’t be replaced by anything are called -----------------
- Productions
- Terminals
- Non-terminals
- All of above
Q21 | Left hand side of a production in CFG consists of:
- One terminal
- More than one terminal
- One non-terminal
- Terminals and non-terminals
Q22 | Choose the incorrect statement:
- (a+b)aa(a+b)generates Regular language.
- A language consisting of all strings over ∑={a,b} having equal number of a’s and b’s is a regular language
- Every language that can be expressed by FA can also be expressed by RE
- None of these
Q23 | Choose the incorrect statement.
- A Mealy machine generates no language as such
- A Mealy machine has no terminal state
- For a given input string, length of the output string generated by a Moore machine is not more than the length of the output string generated by that of a Mealy machine
- All of these
Q24 | In FA, if one enters in a specific state but there is no way to leave it, then that specific state is called
- Dead State
- Waste Basket
- Davey John Locker
- All of these
Q25 | Which statement is true?
- The tape of turing machine is infinite.
- The tape of turing machine is finite.
- The tape of turing machine is infinite when the language is regular
- The tape of turing machine is finite when the language is nonregular.