My Courses

1. All set of polynomial questions which can be solved by a turing machine using a polynomial amount of space: a) PSPACE b) NPSPACE c) EXPSPACE d) None of the mentioned 2. Which of the following problems do not belong to Karp’s 21 NP-complete problems? a) Vertex Cover problems b) Knapsack c) 0-1 integer programming…

1. Complement of regular sets are _________ a) Regular b) CFG c) CSG d) RE 2. Which of the following is true? a) (01)*0 = 0(10)* b) (0+1)*0(0+1)*1(0+1) = (0+1)*01(0+1)* c) (0+1)*01(0+1)*+1*0* = (0+1)* d) All of the mentioned 3. For a _________ state DFA, the time taken for DFA-NFA conversion is O(n). a) n…

1. The minimum number of states required to automate the following Regular Expression: (1) *(01+10) (1) * a) 4 b) 3 c) 2 d) 5 2. If we have more than one accepting states or an accepting state with an outdegree, which of the following actions will be taken? a) addition of new state b)…

1. Number of final state require to accept F in minimal finite automata. a) 1 b) 2 c) 3 d) None of the mentioned 2. State true or false? Statement: An NFA can be modified to allow transition without input alphabets, along with one or more transitions on input symbols. a) True b) False 3.…

1. All the regular languages can have one or more of the following descriptions: i) DFA ii) NFA iii) e-NFA iv) Regular Expressions Which of the following are correct? a) i, ii, iv b) i, ii, iii c) i, iv d) i, ii, iii, iv 2. Which of the following options match the given statement:…

1. According to the given transitions, which among the following are the epsilon closures of q1 for the given NFA? ? (q1, e) = {q2, q3, q4} ? (q4, 1) =q1 ? (q1, e) =q1 a) q4 b) q2 c) q1 d) q1, q2, q3, q4 2. The appropriate precedence order of operations over a…

1. How many languages are over the alphabet R? a) countably infinite b) countably finite c) uncountable finite d) uncountable infinite 2. Complement of a DFA can be obtained by a) making starting state as final state. b) no trival method. c) making final states non-final and non-final to final. d) make final as a…

1. The number of elements in the set for the Language L={x?(?r) *|length if x is at most 2} and ?={0,1} is_________ a) 7 b) 6 c) 8 d) 5 2. What is the output for the given language? Language: A set of strings over ?= {a, b} is taken as input and it prints…

1. Given Language: L= {ab U aba}* If X is the minimum number of states for a DFA and Y is the number of states to construct the NFA, |X-Y|=? a) 2 b) 3 c) 4 d) 1 2. Transition function maps. a) S * Q -> S b) Q * Q -> S c)…

1. A randomized algorithm uses random bits as input inorder to achieve a _____________ good performance over all possible choice of random bits. a) worst case b) best case c) average case d) none of the mentioned 2. PSPACE is strictly the super set of: a) Regular language b) Context free language c) Context Sensitive…