On This Page

This set of Theory of Computation Multiple Choice Questions & Answers (MCQs) focuses on Theory Of Computation Unit 3 Set 1

Q1 | If a language is denoted by a regular expression L = ( x )* (x y x ), then which of the following is not a legal string within L ?
  • yx
  • xyx
  • x
  • xyxyx
Q2 | Given A = {0,1} and L = A*. If R = (0n1n, n > 0), then language L ∪ R and R are respectively
  • Regular, regular
  • Not regular, regular
  • Regular, not regular
  • Context free, not regular
Q3 | If L1 and L2 are context free language and R a regular set, then which one of the languages below is not necessarily a context free language?
  • L1 L2
  • L1 ∩ L2
  • L1 ∩ R
  • L1 ∪ L2
Q4 | The logic of pumping lemma is a good example of
  • Pigeon-hole principle
  • Divide-and-conquer technique
  • Recursion
  • Iteration
Q5 | For two regular languages L1 = (a + b)* a and L2 = b (a + b ) *, the intersection of L1 and L2 is given by
  • (a + b ) * ab
  • ab (a + b ) *
  • a ( a + b ) * b
  • b (a + b ) * a
Q6 | Pumping lemma is generally used for proving that
  • Given grammar is regular
  • Given grammar is not regular
  • Whether two given regular expressions are equivalent or not
  • None of these
Q7 | What is the highest type number which can be applied to the following grammar? S —>Aa, A —> Ba, B —>abc
  • Type 0
  • Type 1
  • Type 2
  • Type 3
Q8 | 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 productionA —>aB {print “(1)” A —> c {print “1”),B —>Ab {print *2”}.When parser is aaacbbb, then string printed
  • 0202021
  • 1202020
  • 1020202
  • None of these
Q9 | FSM can recognize
  • Any grammar
  • Only CG
  • Both (a) and ( b )
  • Only regular grammar
Q10 | Basic limitation of FSM is that it
  • Cannot remember arbitrary large amount of information
  • Sometimes fails to recognize grammars that are regular
  • Sometimes recognizes grammars are not regular
  • None of these
Q11 | 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.
  • 1 and 2
  • 1 and 4
  • 2 and 3
  • 2 and 4
Q12 | If L and L¯ are recursively enumerable, then L is
  • Regular
  • Context free
  • Context sensitive
  • Recursive
Q13 | Which of the following problems is undecidable?
  • Membership problem for CFGs
  • Ambiguity problem for CFGs.
  • Finiteness problem for FSAs.
  • Equivalence problem for FSAs.
Q14 | 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)
  • Context Free Language
  • Context sensitive language
  • Regular language
  • Languages recognizable by Turing machine
Q15 | 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.
  • 1 and 4 only
  • 1 and 3 only
  • 2 only
  • 3 only
Q16 | 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
  • L = {s ε (0+1)* I for every prefix s’ of s, I no(s’)-n1(s’) I ≤ 2}
  • L = {s ε (0+1)* I no(s) mod 7 = n1(s) mod 5 = 0}
  • L = {s ε (0+1)* I no(s) is a 3 digit prime}
  • L = {s ε (0+1)* I no(s)-n1(s) I ≤ 4
Q17 | Which statement is true?
  • The PDA must have one accept state and one reject state
  • The PDA must have one accept state and two reject state
  • The PDA must have two accept state and two reject state
  • There is no reject state in the PDA.
Q18 | Let SHAM3 be the problem of finding a Hamiltonian cycle in a graph G =(V,E)with V divisible by 3 and DHAM3 be the problem of determining if a Hamiltonian cycle exists in such graphs. Which one of the following is true?
  • Both DHAM3 and SHAM3 are NP-hard
  • SHAM3 is NP-hard, but DHAM3 is not
  • DHAM3 is NP-hard, but SHAM3 is not
  • Neither DHAM3 nor SHAM3 is NP-hard
Q19 | Consider the following statements about the context free grammar G = {S - >SS,S - >ab,S ->ba, S - ε}I. G is ambiguousII. G produces all strings with equal number of a’s and b’sIII. G can be accepted by a deterministic PDA.Which combination below expresses all the true statements about G?
  • 1 only
  • 1 and 3
  • 2 and 3
  • 1,2 and 3
Q20 | Consider the regular language L =(111+11111)*. The minimum number of states in any DFA accepting this languages is:
  • 3
  • 5
  • 8
  • 9
Q21 | Give a production grammar for the language L = {x/x ∈ (a,b)*, the number of a’s in x is multiple of 3}.
  • {S->bS,S->b,S->aA,S->bA,A->aB,B->bB,B->aS,S->a}
  • {S->aS,S->bA,A->bB,B->bBa,B->bB}
  • {S->aaS,S->bbA,A->bB,B->ba}
  • None of the above
Q22 | The production Grammar is {S->aSbb,S->abb} is
  • type-3 grammar
  • type-2 grammar
  • type-1 grammar
  • type-0 grammar
Q23 | Regular expression (x/y)(x/y) denotes the set
  • {xy,xy}
  • {xx,xy,yx,yy}
  • {x,y}
  • {x,y,xy}
Q24 | Which one of the following is true regarding FOTRAN?
  • It is a context free language
  • It is a context sensitive language
  • It is a regular language
  • None of the above
Q25 | TM is more powerful than FSM because
  • The tape movement is confined to one direction
  • It has no finite state control
  • It has the capability to remember arbitrary long sequences of input symbols
  • None of these