THEORY of COMPUTATION Multiple Choice Questions :-
1. What is the reason behind a Turing machine is more powerful than finite state machine FSM?
A. turing machine head movement is continued to one direction.
B. turing machine head moment is in both directions i.e. left moment and right moment as well.
C. turing machine has capability remember arbitrary long sequence of input string.
D. all are correct.
Answer:
C. turing machine has capability remember arbitrary long sequence of input string.
2. A pushdown automata behaves like a Turing machine, when it has number of auxiliary/ memory.
A. 0
B. exectly 2
C. 2 or more
D. both exectly 2 or more are correct
Answer:
C. 2 or more
3. The language L = {anbnann≥ 1} is recognized by
A. turing machine
B. 2 pushdown automata
C. post machine
D. all are correct
Answer:
D. all are correct
4. If Turing machine accepts all the words of the languages L and rejects or loops for other words, which are not in L, then L is said to be
A. recursive enumerable
B. recursive
C. context free language (cfl)
D. none of them
Answer:
A. recursive enumerable
5. If a Turing machine halts for each and every world of a language L and rejects other, then L is said to be
A. recursive enumerable
B. recursive
C. context free language
D. none of these
Answer:
C. context free language
6. Universal Turing machine (UTM) influenced the concepts of
A. computability
B. interpretive implementation of programming language
C. program and data is in same memory
D. all are correct
Answer:
D. all are correct
7. The number of symbols necessary to simulate a Turing machine with m symbols and n states
A. 4m × n + m
B. 4m × n + n
C. m+n
D. none of them
Answer:
A. 4m × n + m
8. A universal Turing machine is a
A. reprogrammable truing machine
B. two-tape turing machine
C. single tape turing machine
D. none of them
Answer:
A. reprogrammable truing machine
9. He difference between a read-only Turing machine and a two-way finite state machine is
A. head movement
B. finite control
C. storage capacity
D. power
Answer:
C. storage capacity
10. Which is correct regard an off-line Truing machine?
A. an offline turing machine is a special type of multi-tape turing machine
B. an offline turing machine is a kind of multi-tracks truing machine
C. an offline turing machine is a kind of single-track turing machine
D. none of them
Answer:
A. an offline turing machine is a special type of multi-tape turing machine
11. Which of the following statement is wrong?
A. power of ntm and tm is same
B. for n ≥ 2, npda has some power as a tm
C. for n ≥ 2, npda and 2pda have same power
D. power of ntm and tm is not same
Answer:
D. power of ntm and tm is not same
12. Four pairs are following; in each pair both objects have some common thing. Choose the odd pair;
A. (tm, 2pda)
B. (computer, utm)
C. (2pda, npda)
D. (fa, pda)
Answer:
D. (fa, pda)
13. We think of a Turing machine’s transition function as a
A. computer system
B. software
C. hardware
D. all of them
Answer:
B. software
14. Church’s Thesis supports
A. a turing machine as a general-purpose computer system
B. a turing machine an algorithm and an algorithm as a turing machine
C. both tm is an general-purpose computer and tm is an algorithm and vice-versa are correct
D. none of them is correct
Answer:
C. both tm is an general-purpose computer and tm is an algorithm and vice-versa are correct
15. A random access machine (RAM) and truing machine are different in
A. power
B. accessing
C. storage
D. both accessing and storage are correct
Answer:
D. both accessing and storage are correct
16. Choose the correct statement
A. recursive set ⊆ recursive enumerable set
B. total function is same as partial function
C. recursive sets are analogous to total functions
D. both recursive set ⊆ recursive enumerable set and recursive sets are analogous to total functions are correct.
Answer:
D. both recursive set ⊆ recursive enumerable set and recursive sets are analogous to total functions are correct.
17. Given S = {a, b}, which one of the following sets is not countable?
A. the set all strings over Σ
B. the set of all language over Σ
C. the set of all binary strings
D. the set of all languages over Σ accepted by turing machines
Answer:
B. the set of all language over Σ
18. In which of the stated below is the following statement true?
“For every non-deterministic machine M1, there exists as equivalent deterministic machine M2 recognizing the same language.”
A. m1 is a non-deterministic finite automata
B. m1 is a non-deterministic push-down automata
C. m1 is a non-deterministic turing machine
D. for no machine m1 use the above statement true
Answer:
C. m1 is a non-deterministic turing machine
19. Which of the following conversion is not possible (algorithmically)?
A. regular grammar to context-free grammar
B. non-deterministic finite state automata to deterministic finite state automata
C. non-deterministic pushdown automata to deterministic pushdown automata
D. none deterministic turing machine to deterministic turing machine
Answer:
B. non-deterministic finite state automata to deterministic finite state automata
Unit 1
20. = ∈{ } w has at least as many occurrences of (110)’s as (011)’s}. Let L {w 0,1 *2 = ∈{ } w has at least as many occurrence of (000)’s as (111)’s}. Which one of the following is TRUE?
A. L1 is regular but not L2
B. L2 is regular but not L1
C. Both L1 and L2 are regular
D. Neither L1 nor L2 are regular
Answer:
B. L2 is regular but not L1
21. A spanning tree for a simple graph of order 24 has
A. 12 edges
B. 6 edges
C. 23 edges
D. None of above.
Answer:
C. 23 edges
22. If G is a simple connected 3-regular planar graph where every region is bounded by exactly 3 edges, then the edges of G is
A. 3
B. 4
C. 6
D. 5
Answer:
C. 6
23. If G is a connected planar graph of v vertices e edges and r regions then
A. v-e+r=2
B. e-v+r=2
C. v+e-r=2
D. None of above.
Answer:
A. v-e+r=2
24. A Hamiltonian cycle in a Hamiltonian graph of order 24 has
A. 12 edges.
B. 24 edges
C. 23 edges
D. None of above.
Answer:
B. 24 edges
25. If G is a simple connected 3-regular planar graph where every region is bounded by exactly 3 edges, then the edges of G is
A. 3
B. 4
C. 6
D. 5
Answer:
C. 6
26. The following grammar
G = (N, T, P, S)
N = {S, A, B}
T = {a, b, c}
P : S → aSa
S → aAa
A → bB
B → bB
B → c is
A. is type 3
B. is type 2 but not type 3
C. is type 1 but not type 2
D. is type 0 but not type 1
Answer:
B. is type 2 but not type 3
27. The following grammar
G = (N, T, P, S)
N = {S, A, B, C, D, E}
T = {a, b, c}
P : S → aAB
AB → CD
CD → CE
C → aC
C → b
bE → bc is
A. is type 3
B. is type 2 but not type 3
C. is type 1 but not type 2
D. is type 0 but not type 1
Answer:
C. is type 1 but not type 2
28. The following grammar
G = (N, T, P, S)
N = {S, A, B, C}
T = {a, b, c}
P : S → aS
A → bB
B → cC
C → a is
A. is type 3
B. is type 2 but not type 3
C. is type 1 but not type 2
D. is type 0 but not type 1
Answer:
A. is type 3
29. P, Q, R are three languages. If P & R are regular and if PQ=R, then
A. Q has to be regular
B. Q cannot be regular
C. Q need not be regular
D. Q has to be a CFL
Answer:
C. Q need not be regular
30. Which of the following is true with respect to Kleene’s theorem?
1 A regular language is accepted by a finite automaton.
2 Every language is accepted by a finite automaton or a turingmachine.
A. 1 only
B. 2 only
C. Both 1 and 2 are true statements
D. None is true
Answer:
C. Both 1 and 2 are true statements
31. Automaton accepting the regular expression of any number of a ‘ s is:
A. a*
B. ab*
C. (a/b)*
D. a*b*c
Answer:
A. a*
32. Grammars that can be translated to DFAs:
A. Left linear grammar
B. Right linear grammar
C. Generic grammar
D. All of these
Answer:
B. Right linear grammar
33. Two strings x and y are indistinguishable if:
A. δ*(s, x) = δ* (s, y), i.e. the state reached by a DFA M on input x is the same as the state reached by M on input y
B. if for every string z Є ∑* either both xz and yz are in language A on ∑* or both xz and yz are not in A
C. Both above statements are true
D. None of the above
Answer:
C. Both above statements are true
34. Given an arbitrary non-deterministic finite automaton NFA with N states, the maximum number of states in an equivalent minimized DFA is at least:
A. N2
B. 2N
C. 2N
D. N!
Answer:
C. 2N
35. Regular expressions are
A. Type 0 language
B. Type 1 language
C. Type 2 language
D. Type 3 language
Answer:
A. Type 0 language
36. The regular expression 0*(10)* denotes the same set as
A. (1*0)*1*
B. 0+(0+10)*
C. (0+1)*10(0+1)*
D. None of the above
Answer:
B. 0+(0+10)*
37. Consider the NFA M shown below. Let the language accepted by M be L. Let L1 be the language accepted by the NFA M1, obtained by changing the accepting state of M to a non-accepting state and by changing the non-accepting state of M to accepting states. Which of the following statements is true?
A. L1 = {0,1}* − L
B. L1 = {0,1}*
C. L1 is a subset of L
D. L1 = L
Answer:
A. L1 = {0,1}* − L
38. Which of the statements is true:
A. The complement of a regular language is always regular.
B. Homomorphism of a regular language is always regular.
C. Both of the above are true statements
D. None of the above
Answer:
C. Both of the above are true statements
39. The regular sets are closed under:
A. Union
B. Concatenation
C. Kleene closure
D. All of the above
Answer:
D. All of the above
40. Any given transition graph has an equivalent:
A. regular
B. DFSM (Deterministic Finite State Machine)
C. NDFSM
D. All of them
Answer:
D. All of them
41. A language is regular if and only if
A. Accepted by DFA
B. Accepted by PDA
C. Accepted by LBA
D. Accepted by Turing machine
Answer:
A. Accepted by DFA
42. Which of the following is not a regular expression?
A. [(a+b)*-(aa+bb)]*
B. [(0+1)-(0b+a1)*(a+b)]*
C. (01+11+10)*
D. (1+2+0)*(1+2)*
Answer:
B. [(0+1)-(0b+a1)*(a+b)]*
43. Consider the regular language L = (111+111111)*. The minimum number of states inany DFA accepting this language is
A. 3
B. 5
C. 8
D. 9
Answer:
D. 9
44. How many strings of length less than 4 contains the language described by the regular expression (x+y)*y(a+ab)*?
A. 7
B. 10
C. 12
D. 11
Answer:
D. 11
45. Which of the following is TRUE?
A. Every subset of a regular set is regular
B. Every finite subset of a non-regular set is regular
C. The union of two non-regular sets is not regular
D. Infinite union of finite sets is regular
Answer:
B. Every finite subset of a non-regular set is regular
46. The minimum state automaton equivalent to the above FSA has the following number of states
A. 1
B. 2
C. 3
D. 4
Answer:
B. 2
47. Which one of the following languages over the alphabet {0,1} is described
by the regular expression: (0+1)*0(0+1)*0(0+1)*?
A. The set of all strings containing the substring 00.
B. The set of all strings containing at most two 0’s.
C. The set of all strings containing at least two 0’s.
D. The set of all strings that begin and end with either 0 or 1.
Answer:
C. The set of all strings containing at least two 0’s.
48. Let w be any string of length n is {0,1}*. Let L be the set of all substrings of w. What is the minimum number of states in a non-deterministic finite automaton that accepts L?
A. n-1
B. n
C. n+1
D. 2n-1
Answer:
C. n+1
49. Which of the following are regular sets?
A. I and IV only
B. I and III only
C. I only
D. IV only
Answer:
A. I and IV only
50. A minimum state deterministic finite automation accepting the language L={W W ε {0,1}*, number of 0s and 1s in are divisible by 3 and 5, respectively} has
A. 15 states
B. 11 states
C. 10 states
D. 9 states
Answer:
A. 15 states
51. Let P be a regular language and Q be context-free language such that Q ∈ P. (For example, let P be the language represented by the regular expression p*q* and Q be {pnqn
n∈ N}). Then which of the following is ALWAYS regular?
A. P ∩ Q
B. P – Q
C. ∑* – P
D. ∑* – Q
Answer:
C. ∑* – P
52. Given a Non-deterministic Finite Automation (NFA) with states p and r as initial and final states respectively and transition table as given below:
A B
P – Q
q R S
r R S
s R S
The minimum number of states required in Deterministic Finite Automation
(DFA) equivalent to NFA is
A. 5
B. 4
C. 3
D. 2
Answer:
C. 3
53. Which one of the following statement is true for a regular language L over {a} whose minimal finite state automation has two states?
A. L must be either {an I n is odd} or {an I n is even}
B. L must be {an I n is odd}
C. L must be {an I n is even}
D. L must be {an I n = 0}
Answer:
A. L must be either {an I n is odd} or {an I n is even}
54. The …………. is said to be ambiguous if there exist at least one word of its language that can be generated by the different production tree .
A. CFL
B. CFG
C. GTG
D. None of the given
Answer:
B. CFG
Unit 2
55. Type-1 Grammar is known as_____________
A. CFG
B. CSG
C. REGULAR
D. All
Answer:
B. CSG
56. If G is “S → a S/a”, then L(G) = ?
A. a*
B. ^
C. {a}+
D. Both (a) & (c)
Answer:
C. {a}+
57. “S →a S”, what is the type of this production?
A. Type 0
B. Type 1
C. Type 2
D. Type 3
Answer:
D. Type 3
58. A→abA a type __________productions
A. Type 0
B. Type 1
C. Type 2
D. Type 3
Answer:
B. Type 1
59. The following CFG is in
S → AB**spaceB → CD**spaceB → AD**spaceB → b**spaceD → AD**spaceD → d**spaceA → a**spaceC → a
A. Chomsky normal form but not strong Chomsky normal form
B. Weak Chomsky normal form but not Chomsky normal form
C. Strong Chomsky normal form
D. Greibach normal form
Answer:
C. Strong Chomsky normal form
60. The language accepted by a Push down Automata:
A. Type0
B. Type1
C. Type2
D. Type3
Answer:
C. Type2
61. Which of the following problems is undecidable?
A. Membership problem for CFGs
B. Ambiguity problem for CFGs
C. Finiteness problem for Finite state automata FSAs
D. Equivalence problem for FSAs
Answer:
B. Ambiguity problem for CFGs
62. Which one of the following statement is FALSE?
A. context-free languages are closed under union
B. context-free languages are closed under concatenation
C. context-free languages are closed under intersection
D. context-free languages are closed under Kleene closure
Answer:
C. context-free languages are closed under intersection
63. Which of the following strings is not generated by the following grammar? S → SaSbS
ε
A. aabb
B. abab
C. aababb
D. aaabb
Answer:
D. aaabb
64. Which of the following regular expression identity is true?
A. r(*) = r*
B. (r*s*)* = (r + s)*
C. (r + s)* = r* + s*
D. r*s* = r* + s*
Answer:
B. (r*s*)* = (r + s)*
65. A language L is accepted by a FSA iff it is
A. CFL
B. CSL
C. Recursive
D. Regular
Answer:
D. Regular
66. Consider the following CFG
S → aB S → bA**spaceB → b A → a**spaceB → bS A → aS**spaceB → aBB A → bAA**spaceConsider the following derivation**spaceS ⇒aB**space⇒aaBB**space⇒aaBb**space⇒aabSb**space⇒aabbAb**space⇒aabbab**spaceThis derivation is
A. A leftmost derivation
B. A rightmost derivation
C. Both leftmost and rightmost derivation
D. Neither leftmost nor rightmost derivation
Answer:
D. Neither leftmost nor rightmost derivation
67. Consider the following language L = {anbncndn
n ≥ 1} L is
A. CFL but not regular
B. CSL but not CFL
C. Regular
D. Type 0 language but not type 1
Answer:
B. CSL but not CFL
68. A language is represented by a regular expression (a)*(a + ba). Which of the following strings does not belong to the regular set represented by the above expression?
A. aaa
B. aba
C. abab
D. aa
Answer:
C. abab
69. Which of the following denotes Chomskianhiearchy?
A. REG ⊂ CFL ⊂ CSL ⊂ type0
B. CFL ⊂ REG ⊂ type0 ⊂ CSL
C. CSL ⊂ type0 ⊂ REG ⊂ CFL
D. CSL ⊂ CFL ⊂ REG ⊂ type0
Answer:
A. REG ⊂ CFL ⊂ CSL ⊂ type0
70. The concept of FSA is much used in this part of the compiler
A. Lexical analysis
B. Parser
C. Code generation
D. Code optimization
Answer:
A. Lexical analysis
71. The following grammar
G = (N, T, P, S)**spaceN = {S, A, B, C, D, E}**spaceT = {a, b, c}**spaceP : S → aAB**spaceAB → CD**spaceCD → CE**spaceC → aC**spaceC → b**spacebE → bc is
A. is type 3
B. is type 2 but not type 3
C. is type 1 but not type 2
D. is type 0 but not type 1
Answer:
C. is type 1 but not type 2
72. The following CFG is in
S → aBB**spaceB → bAA**spaceA → a**spaceB → b
A. Chomsky normal form but not strong Chomsky normal form
B. Weak Chomsky normal form but not Chomsky normal form
C. Strong Chomsky normal form
D. Greibach normal form
Answer:
D. Greibach normal form
73. Which of the following statements is wrong?
A. The regular sets are closed under intersection
B. The class of regular sets is closed under substitution
C. The class of regular sets is closed under homomorphism
D. Context Sensitive Grammar(CSG) can be recognized by Finite State Machine
Answer:
D. Context Sensitive Grammar(CSG) can be recognized by Finite State Machine
74. Context free grammar is not closed under
A. Product operation
B. Union
C. Complementation
D. kleene star
Answer:
C. Complementation
Unit 3
75. Which of the following statement is wrong?
A. Any regular language can be generated by a context-free grammar
B. Some non-regular languages cannot be generated by any CFG
C. the intersection of a CFL and regular set is a CFL
D. All non-regular languages can be generated by CFGs.
Answer:
D. All non-regular languages can be generated by CFGs.
76. Let the class of language accepted by finite state machine be L1 and the class of languages represented by regular expressions be L2 then
A. L1
B. L1>=L2
C. L1 U L2 = .*
D. L1=L2
Answer:
D. L1=L2
77. Which of the following statement is wrong?
A. Any regular language has an equivalent context-free grammar.
B. Some non-regular languages can’t be generated by any context-free grammar
C. Intersection of context free language and a regular language is always context-free
D. All languages can be generated by context- free grammar
Answer:
D. All languages can be generated by context- free grammar
78. Grammar that produce more than one Parse tree for same sentence is:
A. Ambiguous
B. Unambiguous
C. Complementation
D. Concatenation
Answer:
A. Ambiguous
79. The language accepted by a Push down Automata:
A. Type 0
B. Type 1
C. Type 2
D. Type 3
Answer:
C. Type 2
80. The PDA is called non-deterministic PDA when there are more than one out going edges from……… state:
A. START or READ
B. POP or REJECT
C. READ or POP
D. PUSH or POP
Answer:
C. READ or POP
81. 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 :
A. Non regular language of L
B. Complement of the language L
C. None of the given
D. All of above
Answer:
B. Complement of the language L
82. 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:
A. String
B. Regular language
C. Null string
D. None of the above
Answer:
C. Null string
83. 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?
A. (0*10*1)*
B. 0*(10*10*)*
C. 0*(10*1*)*0*
D. 0*1(10*1)*10*
Answer:
B. 0*(10*10*)*
84. Consider the following Finite State Automaton The language accepted by this automaton is given by the regular expression
A. b*ab*ab*ab
B. (a+b)*
C. b*a(a+b)*
D. b*ab*ab
Answer:
C. b*a(a+b)*
85. 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?
A. L2-L1 is recursively enumerable
B. L1-L3 is recursively enumerable
C. L2 intersection L1 is recursively enumerable
D. L2 union L1 is recursively enumerable
Answer:
B. L1-L3 is recursively enumerable
86. Let L denotes the language generated by the grammar S – OSO/00. Which of the
following is true?
A. L = O
B. L is regular but not O
C. L is context free but not regular
D. L is not context free
Answer:
B. L is regular but not O
87. 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?
A. ScT (S is a subset of T)
B. TcS (T is a subset of S)
C. S=T
D. SnT=Ø
Answer:
C. S=T
88. Which of the following pairs have DIFFERENT expressive power?
A. Deterministic finite automata (DFA) and Non-Deterministic finite automata(NFA)
B. Deterministic push down automata (DPDA) and Non-deterministic pushdown automata
C. Deterministic single-tape Turing machine and Non-deterministic single-tape Turing Machine
D. Single-tape Turing machine and multi-tape Turing machine
Answer:
B. Deterministic push down automata (DPDA) and Non-deterministic pushdown automata
89. 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
A. P-4, Q-1, R-2, S-3
B. P-3, Q-1, R-4, S-2
C. P-3, Q-4, R-1, S-2
D. P-2, Q-1, R-4, S-3
Answer:
B. P-3, Q-1, R-4, S-2
90. 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
A. 15 states
B. 11 states
C. 10 states
D. 9 states
Answer:
A. 15 states
Unit 3
91. Any Language generated by an unrestricted grammar is:
A. Recursive
B. Recursively Enumerable
C. Not Recursive
D. None of the above
Answer:
A. Recursive
92. The Family of recursive language is not closed under which of the following operations:
A. Union
B. Intersection
C. Complementation
D. None of the above.
Answer:
D. None of the above.
93. PCP is:
A. Decidable
B. Undecidable
C. Sometimes Decidable
D. None of the
Answer:
B. Undecidable
94. If PCP is decidable then MPCP is
A. Decidable
B. Undecidable
C. Can’t Say
D. None of the
Answer:
C. Can’t Say
95. 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
A. NP hard
B. NP complete
C. Recursive
D. Recursively enumerable
Answer:
D. Recursively enumerable
96. Consider the following statements
I. Recursive languages are closed under complementation
II. Recursively enumerable languages are closed under union
III. Recursively enumerable languages are closed under complementation
Which of the above statement are TRUE?
A. I only
B. I and II
C. I and III
D. II and III
Answer:
B. I and II
97. Recursively enumerable languages are not closed under
A. Union
B. homomorphism
C. complementation
D. concatenation
Answer:
C. complementation
98. Which of the following problem is undecidable?
A. Membership problem for CFL
B. Membership problem for regular sets
C. Membership problem for CSL
D. Membership problem for type 0 languages
Answer:
D. Membership problem for type 0 languages
99. Recursive languages are
A. A proper superset of CFL
B. Always recognized by PDA
C. Are also called type 0 languages
D. Always recognized by FSA
Answer:
A. A proper superset of CFL
100. 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?
A. X is decidable
B. X is undecidable but partially decidable
C. X is undecidable and not even partially decidable
D. X is not a decision problem
Answer:
A. X is decidable
101. 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 ?
A. yx
B. xyx
C. x
D. xyxyx
Answer:
D. xyxyx
102. Given A = {0,1} and L = A*. If R = (0n1n, n > 0), then language L ∪ R and R are respectively
A. Regular, regular
B. Not regular, regular
C. Regular, not regular
D. Context free, not regular
Answer:
D. Context free, not regular
103. 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?
A. L1 L2
B. L1 ∩ L2
C. L1 ∩ R
D. L1 ∪ L2
Answer:
B. L1 ∩ L2
104. The logic of pumping lemma is a good example of
A. Pigeon-hole principle
B. Divide-and-conquer technique
C. Recursion
D. Iteration
Answer:
A. Pigeon-hole principle
105. For two regular languages L1 = (a + b)* a and L2 = b (a + b ) *, the intersection of L1 and L2 is given by
A. (a + b ) * ab
B. ab (a + b ) *
C. a ( a + b ) * b
D. b (a + b ) * a
Answer:
D. b (a + b ) * a
106. Pumping lemma is generally used for proving that
A. Given grammar is regular
B. Given grammar is not regular
C. Whether two given regular expressions are equivalent or not
D. None of these
Answer:
B. Given grammar is not regular
107. What is the highest type number which can be applied to the following grammar?
S —>Aa, A —> Ba, B —>abc
A. Type 0
B. Type 1
C. Type 2
D. Type 3
Answer:
C. Type 2
108. 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 production
A —>aB {print “(1)” A —> c {print “1”),
B —>Ab {print *2”}.
When parser is aaacbbb, then string printed
A. 0202021
B. 1202020
C. 1020202
D. None of these
Answer:
A. 0202021
109. FSM can recognize
A. Any grammar
B. Only CG
C. Both (a) and ( b )
D. Only regular grammar
Answer:
D. Only regular grammar
110. Basic limitation of FSM is that it
A. Cannot remember arbitrary large amount of information
B. Sometimes fails to recognize grammars that are regular
C. Sometimes recognizes grammars are not regular
D. None of these
Answer:
A. Cannot remember arbitrary large amount of information
111. 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.
A. 1 and 2
B. 1 and 4
C. 2 and 3
D. 2 and 4
Answer:
B. 1 and 4
112. If L and L¯ are recursively enumerable, then L is
A. Regular
B. Context free
C. Context sensitive
D. Recursive
Answer:
D. Recursive
113. Which of the following problems is undecidable?
A. Membership problem for CFGs
B. Ambiguity problem for CFGs.
C. Finiteness problem for FSAs.
D. Equivalence problem for FSAs.
Answer:
B. Ambiguity problem for CFGs.
114. 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)
A. Context Free Language
B. Context sensitive language
C. Regular language
D. Languages recognizable by Turing machine
Answer:
D. Languages recognizable by Turing machine
115. 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.
A. 1 and 4 only
B. 1 and 3 only
C. 2 only
D. 3 only
Answer:
C. 2 only
116. 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 for every prefix s’ of s, I no(s’)-n1(s’) I ≤ 2}
B. L = {s ε (0+1)* I no(s) mod 7 = n1(s) mod 5 = 0}
C. L = {s ε (0+1)* I no(s) is a 3 digit prime}
D. L = {s ε (0+1)* I no(s)-n1(s) I ≤ 4
Answer:
D. L = {s ε (0+1)* I no(s)-n1(s) I ≤ 4
117. Which statement is true?
A. The PDA must have one accept state and one reject state
B. The PDA must have one accept state and two reject state
C. The PDA must have two accept state and two reject state
D. There is no reject state in the PDA.
Answer:
D. There is no reject state in the PDA.
118. 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?
A. Both DHAM3 and SHAM3 are NP-hard
B. SHAM3 is NP-hard, but DHAM3 is not
C. DHAM3 is NP-hard, but SHAM3 is not
D. Neither DHAM3 nor SHAM3 is NP-hard
Answer:
A. Both DHAM3 and SHAM3 are NP-hard
119. Consider the following statements about the context free grammar G = {S – >SS,S – >ab,S ->ba, S – ε}
I. G is ambiguous
II. G produces all strings with equal number of a’s and b’s
III. G can be accepted by a deterministic PDA.
Which combination below expresses all the true statements about G?
A. 1 only
B. 1 and 3
C. 2 and 3
D. 1,2 and 3
Answer:
D. 1,2 and 3
120. Consider the regular language L =(111+11111)*. The minimum number of states in any DFA accepting this languages is:
A. 3
B. 5
C. 8
D. 9
Answer:
D. 9
121. Give a production grammar for the language L = {x/x ∈ (a,b)*, the number of a’s in x is multiple of 3}.
A. {S->bS,S->b,S->aA,S->bA,A->aB,B->bB,B->aS,S->a}
B. {S->aS,S->bA,A->bB,B->bBa,B->bB}
C. {S->aaS,S->bbA,A->bB,B->ba}
D. None of the above
Answer:
A. {S->bS,S->b,S->aA,S->bA,A->aB,B->bB,B->aS,S->a}
122. The production Grammar is {S->aSbb,S->abb} is
A. type-3 grammar
B. type-2 grammar
C. type-1 grammar
D. type-0 grammar
Answer:
B. type-2 grammar
123. Regular expression (x/y)(x/y) denotes the set
A. {xy,xy}
B. {xx,xy,yx,yy}
C. {x,y}
D. {x,y,xy}
Answer:
B. {xx,xy,yx,yy}
Unit 4
124. Which one of the following is true regarding FOTRAN?
A. It is a context free language
B. It is a context sensitive language
C. It is a regular language
D. None of the above
Answer:
B. It is a context sensitive language
125. TM is more powerful than FSM because
A. The tape movement is confined to one direction
B. It has no finite state control
C. It has the capability to remember arbitrary long sequences of input symbols
D. None of these
Answer:
B. It has no finite state control
126. 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 :
A. (0+1+2)*
B. 0*1*2*
C. 0* + 1 + 2
D. (0+1)*2*
Answer:
B. 0*1*2*
Unit 4
127. Suppose that a problem A is known to have a polynomial-time verification algorithm. Which of the following statements can be deduced.
A. A is in NP.
B. A is in NP but not P
C. A is in both NP and P.
D. A is NP-complete.
Answer:
B. A is in NP but not P
128. 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.
A. Assertions (a) and (b) are both true.
B. Neither (a) nor (b) is true.
C. Both False
D. None of above
Answer:
C. Both False
129. A PC not connected to a network is equivalent to
A. A Deterministic Finite-State Automaton,
B. A Turing Machine,
C. A Push-Down Automaton,
D. None of the above.
Answer:
A. A Deterministic Finite-State Automaton,
130. Recursively enumerable languages are not closed under:
A. Union
B. Intersection
C. Complementation
D. Concatenation
Answer:
C. Complementation
131. 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?
A. (L1)’ is recursive and (L2)’ is recursively enumerable
B. (L1)’ is recursive and (L2)’ is not recursively enumerable
C. (L1)’ and (L2)’ are recursively enumerable
D. (L1)’ is recursively enumerable and (L2)’ is recursive
Answer:
B. (L1)’ is recursive and (L2)’ is not recursively enumerable
132. 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?
A. R is NP-complete
B. R is NP-hard
C. Q is NP-complete
D. Q is NP-hard
Answer:
A. R is NP-complete
133. 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?
A. L is recursively enumerable, but not recursive
B. L is recursive, but not context-free
C. L is context-free, but not regular
D. L is regular
Answer:
D. L is regular
134. A FSM can be considered, having finite tape length without rewinding capability and unidirectional tape movement
A. Turing machine
B. Pushdown automata
C. Context free languages
D. Regular languages
Answer:
A. Turing machine
135. Which of the following statement is true?
A. All languages can be generated by CFG
B. The number of symbols necessary to simulate a Turing Machine(TM) with m symbols and n states is mn.
C. Any regular languages have an equivalent CFG.
D. The class of CFG is not closed under union.
Answer:
C. Any regular languages have an equivalent CFG.
136. Recursively enumerable languages are not closed under
A. Complementation
B. Union
C. Intersection
D. None of the above
Answer:
A. Complementation
137. The following CFG is in
S → aBB
B → bAA
A → a
B → b
A. Chomsky normal form but not strong Chomsky normal form
B. Weak Chomsky normal form but not Chomsky normal form
C. Strong Chomsky normal form
D. Greibach normal form
Answer:
D. Greibach normal form
138. The languages ————– are the examples of non regular languages.
A. PALINDROME and PRIME
B. PALINDROME and EVEN-EVEN
C. EVEN-EVEN and PRIME
D. FACTORIAL and SQURE
Answer:
A. PALINDROME and PRIME
139. 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
A. Complement of L
B. Pumping Lemma
C. Kleene’s theorem
D. None in given
Answer:
B. Pumping Lemma
140. Languages are proved to be regular or non regular using pumping lemma.
A. True
B. False
C. Not always true
D. can’t say anything
Answer:
A. True
141. ___________ states are called the halt states.
A. ACCEPT and REJECT
B. ACCEPT and READ
C. ACCEPT AND START
D. ACCEPT AND WRITE
Answer:
A. ACCEPT and REJECT
142. The part of an FA, where the input string is placed before it is run, is called _______
A. State
B. Transition
C. Input Tape
D. Output Tape
Answer:
C. Input Tape
143. The PDA is called non-deterministic PDA when there are more than one out going edges from……… state
A. START or READ
B. POP or REJECT
C. READ or POP
D. PUSH or POP
Answer:
C. READ or POP
144. If an effectively solvable problem has answered in yes or no, then this
solution is called
A. Decision procedure
B. Decision method
C. Decision problem
D. Decision making
Answer:
A. Decision procedure
145. The symbols that can’t be replaced by anything are called —————–
A. Productions
B. Terminals
C. Non-terminals
D. All of above
Answer:
B. Terminals
146. Left hand side of a production in CFG consists of:
A. One terminal
B. More than one terminal
C. One non-terminal
D. Terminals and non-terminals
Answer:
D. Terminals and non-terminals
147. Choose the incorrect statement:
A. (a+b)aa(a+b)generates Regular language.
B. A language consisting of all strings over ∑={a,b} having equal number of a’s and b’s is a regular language
C. Every language that can be expressed by FA can also be expressed by RE
D. None of these
Answer:
D. None of these
148. Choose the incorrect statement.
A. A Mealy machine generates no language as such
B. A Mealy machine has no terminal state
C. 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
D. All of these
Answer:
C. 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
149. In FA, if one enters in a specific state but there is no way to leave it, then that specific state is called
A. Dead State
B. Waste Basket
C. Davey John Locker
D. All of these
Answer:
D. All of these
150. Which statement is true?
A. The tape of turing machine is infinite.
B. The tape of turing machine is finite.
C. The tape of turing machine is infinite when the language is regular
D. The tape of turing machine is finite when the language is nonregular.
Answer:
A. The tape of turing machine is infinite.
151. If r1 = (aa + bb) and r2 = (a + b) then the language (aa + bb)(a + b) will be generated by Select correct option:
A. (r1)(r2)
B. (r1 + r2)
C. (r2)(r1)
D. (r1)
Answer:
A. (r1)(r2)
152. Which of the following will be used for text searching application-?
A. NFA
B. DFA
C. PDA
D. None of these
Answer:
C. PDA
153. Context free grammar is used for-
A. Lexical analyzer
B. Document type definition (DTD)
C. Text pattern searching
D. Both a & c
Answer:
B. Document type definition (DTD)
154. The set strings of 0’s and 1’s with atmost one pair consecutive one’s-
A. (0+1)*(01)(10)(0+1)*
B. (0+1)*(01)*(10)(0+1)*
C. (0+1)*(01)(10)*(0+1)*
D. (0+!)(01)*(10)*(0+1)
Answer:
D. (0+!)(01)*(10)*(0+1)
155. The problem 3-SAT and 2-SAT are
A. Both in P
B. Both NP complete
C. NP-complete and in P respectively
D. Undecidable and NP-complete respectively
Answer:
C. NP-complete and in P respectively
156. Which of the following instances of the post correspondence problem has a viable sequence (a solution)?
A. {(b, bb), (bb, bab), (bab, abb), (abb, babb)}
B. {(ab, aba), (baa, aa), (aba, baa)}
C. {(ab, abb), (ba, aaa), (aa, a)}
D. none of the above
Answer:
C. {(ab, abb), (ba, aaa), (aa, a)}
157. 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?
A. Both FHAM and DHAM are NP-hard
B. FHAM is NP hard, but DHAM is not
C. DHAM is NP hard, but FHAM is not
D. Neither FHAM nor DHAM is NP hard
Answer:
A. Both FHAM and DHAM are NP-hard
158. 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.
A. P3 has polynomial time solution if P1 is polynomial time reducible to P3
B. P3 is NP complete if P3 is polynomial time reducible to P2
C. P3 is NP complete if P2 is reducible to P3
D. P3 has polynomial time complexity and P3 is reducible to P2
Answer:
C. P3 is NP complete if P2 is reducible to P3
159. Which one of the following is the strongest correct statement about a finite language Lover a finite alphabet Σ?
A. L is undecidable
B. L is recursive
C. L is a CSL
D. L is a regular set
Answer:
D. L is a regular set
160. Which one of the following is not decidable?
A. given a Turing machine M, a string s, and an integer k, M accepts s with k steps
B. equivalence of two given Turing machines
C. language accepted by a given DFSA is nonempty
D. language generated by a CFG is nonempty
Answer:
B. equivalence of two given Turing machines
161. 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.
A. 1, 2 and 3
B. 1 and 2 only
C. 2 and 3 only
D. 1 and 3 only
Answer:
A. 1, 2 and 3
162. 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
A. Only DHAM3 is NP-hard
B. Only SHAM3 is NP-hard
C. Both SHAM3 and DHAM3 are NP-hard
D. Neither SHAM3 nor DHAM3 is NP-hard
Answer:
C. Both SHAM3 and DHAM3 are NP-hard
163. Which of the following statement is false for a turing machine?
A. There exists an equivalent deterministic turing machine for every nondeterministic turing machine
B. Turing decidable languages are closed under intersection and complementation
C. Turing recognizable languages are closed under union and intersection
D. Turing recognizable languages are closed under union and complementation
Answer:
D. Turing recognizable languages are closed under union and complementation
164. 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
A. P is NP-complete
B. P is NP-hard but not NP-complete
C. P is in NP but not NP-complete
D. P is neither NP-hard nor in NP
Answer:
A. P is NP-complete
165. 3-SAT and 2-SAT problems are
A. NP-complete and in P respectively
B. Undecidable and NP-complete
C. Both NP-complete
D. Both in P
Answer:
A. NP-complete and in P respectively
166. 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
A. 2k + 1
B. k + 1
C. 2n + 1
D. n + 1
Answer:
D. n + 1
167. Consider a stack, which is limited to 10 items. The language accepted by a push- down automaton in such stack is best described as
A. Regular
B. Deterministic context free
C. Context free
D. Recursive
Answer:
A. Regular
168. 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
A. 2
B. 7
C. 4
D. 3
Answer:
D. 3
169. 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 decidable if P3 is reducible to compliment of P2
B. P3 is decidable if P1 is reducible to P3
C. P3 is undecidable if P1 is reducible to P3
D. P3 is undecidable if P2 is reducible to P3
Answer:
D. P3 is undecidable if P2 is reducible to P3
170. The set which is not countable if we have ∑ = {a, b}, is
A. Set of all languages over ∑ accepted by turing machine
B. Set of all regular languages over ∑
C. Set of all strings over ∑
D. Set of all languages over ∑
Answer:
D. Set of all languages over ∑
171. 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?
A. n+1
B. n+2
C. n
D. 2n
Answer:
B. n+2
172. 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
A. 10
B. 01
C. 101
D. 110
Answer:
A. 10
173. The set that can be recognized by a deterministic finite state automaton is
A. The set {1, 101, 11011, 1110111, …….}
B. The set of binary string in which the number of 0’s is same as the number of1’s
C. 1, 2, 4, 8……2n ….. written in binary
D. 1, 2, 4, 8……2n ….. written in unary
Answer:
C. 1, 2, 4, 8……2n ….. written in binary