Theory Of Computation Unit 2 Set 1
On This Page
This set of Theory of Computation Multiple Choice Questions & Answers (MCQs) focuses on Theory Of Computation Unit 2 Set 1
Q1 | Let the class of language accepted by finite state machine be L1 and the class of languages represented by regular expressions be L2 then
- L1
- L1>=L2
- L1 U L2 = .*
- L1=L2
Q2 | Which of the following statement is wrong?
- Any regular language has an equivalent context-free grammar.
- Some non-regular languages can’t be generated by any context-free grammar
- Intersection of context free language and a regular language is always context-free
- All languages can be generated by context- free grammar
Q3 | Grammar that produce more than one Parse tree for same sentence is:
- Ambiguous
- Unambiguous
- Complementation
- Concatenation
Q4 | The language accepted by a Push down Automata:
- Type 0
- Type 1
- Type 2
- Type 3
Q5 | 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
Q6 | Let L be a language defined over an alphabet ∑,then the language of strings , defined over ∑, not belonging to L denoted by LC or L. is called :
- Non regular language of L
- Complement of the language L
- None of the given
- All of above
Q7 | All NonNull words of the CFL can be generated by the corresponding CFG which is in CNF i.e the grammar in CNF will generate the same language except the:
- String
- Regular language
- Null string
- None of the above
Q8 | Let L={w (0 + 1)*w has even number of 1s}, i.e. L is the set of all bit strings with even number of 1s. Which one of the regular expression below represents L?
- (0*10*1)*
- 0*(10*10*)*
- 0*(10*1*)*0*
- 0*1(10*1)*10*
Q9 | Consider the following Finite State Automaton The language accepted by this automaton is given by the regular expression
- b*ab*ab*ab
- (a+b)*
- b*a(a+b)*
- b*ab*ab
Q10 | Let L1 be a recursive language. Let L2 and L3 be languages that are recursively enumerable but not recursive. Which of the following statements is not necessarily true?
- L2-L1 is recursively enumerable
- L1-L3 is recursively enumerable
- L2 intersection L1 is recursively enumerable
- L2 union L1 is recursively enumerable
Q11 | Let L denotes the language generated by the grammar S – OSO/00. Which of thefollowing is true?
- L = O
- L is regular but not O
- L is context free but not regular
- L is not context free
Q12 | Let S and T be language over ={a,b} represented by the regular expressions (a+b*)* and (a+b)*, respectively. Which of the following is true?
- ScT (S is a subset of T)
- TcS (T is a subset of S)
- S=T
- SnT=Ø
Q13 | Which of the following pairs have DIFFERENT expressive power?
- Deterministic finite automata (DFA) and Non-Deterministic finite automata(NFA)
- Deterministic push down automata (DPDA) and Non-deterministic pushdown automata
- Deterministic single-tape Turing machine and Non-deterministic single-tape Turing Machine
- Single-tape Turing machine and multi-tape Turing machine
Q14 | Match all items in Group 1 with correct options from those given in Group 2.List I List II**spaceP. Regular Expression 1. Syntax analysis**spaceQ. Push down automata 2. Code Generation**spaceR. Dataflow analysis 3. Lexical analysis**spaceS. Register allocation 4. Code optimization
- P-4, Q-1, R-2, S-3
- P-3, Q-1, R-4, S-2
- P-3, Q-4, R-1, S-2
- P-2, Q-1, R-4, S-3
Q15 | A minimum state deterministic finite automation accepting the language L = {W W € {0,1}* , number of 0's and 1's in W are divisible by 3 and 5 respectively has
- 15 states
- 11 states
- 10 states
- 9 states
Q16 | Any Language generated by an unrestricted grammar is:
- Recursive
- Recursively Enumerable
- Not Recursive
- None of the above
Q17 | The Family of recursive language is not closed under which of the followingoperations:
- Union
- Intersection
- Complementation
- None of the above.
Q18 | PCP is:
- Decidable
- Undecidable
- Sometimes Decidable
- None of the
Q19 | If PCP is decidable then MPCP is
- Decidable
- Undecidable
- Can’t Say
- None of the
Q20 | Consider a language L for which there exists a Turing machine ™, T, that accepts every word in L and either rejects or loops for every word that is not in L. The language L is
- NP hard
- NP complete
- Recursive
- Recursively enumerable
Q21 | Consider the following statementsI. Recursive languages are closed under complementationII. Recursively enumerable languages are closed under unionIII. Recursively enumerable languages are closed under complementationWhich of the above statement are TRUE?
- I only
- I and II
- I and III
- II and III
Q22 | Recursively enumerable languages are not closed under
- Union
- homomorphism
- complementation
- concatenation
Q23 | Which of the following problem is undecidable?
- Membership problem for CFL
- Membership problem for regular sets
- Membership problem for CSL
- Membership problem for type 0 languages
Q24 | Recursive languages are
- A proper superset of CFL
- Always recognized by PDA
- Are also called type 0 languages
- Always recognized by FSA
Q25 | Consider the following problem x. Given a Turing machine M over the input alphabet Σ, any state q of M. And a word w Є Σ*, does the computation of M on w visit the state q? Which of the following statements about x is correct?
- X is decidable
- X is undecidable but partially decidable
- X is undecidable and not even partially decidable
- X is not a decision problem