Theory of Computation MCQ 2
This page is provided with simple multiple choice questions in Theory of computation.
If the reader want to learn all the concepts of theory of computation. Click Here.
At learning monkey one can learn all the computer science subjects from basics to advanced and GATE for free. Click Here.
1) If ∑= {0,1}, then Ф* will result to:
1) ε
2) Ф
3) ∑
4) None of the mentioned
Answer: 1
2) Which of the following represents a language which has no pair of consecutive 1’s if ∑= {0,1}?
1) (0+10)*(1+ε)
2) (0+10)*(1+ε)*
3) (0+101)*(0+ε)
4) (1+010)*(1+ε)
Answer: 2
3) The finite automata accept the following languages:
1) Context Free Languages
2) Context Sensitive Languages
3) Regular Languages
4) All the mentioned
Answer: 3
4) (a + b*c) most correctly represents:
1) (a +b) *c
2) (a)+((b)*.c)
3) (a + (b*)).c
4) a+ ((b*).c)
Answer: 4
5) Which of the following regular expressions represents the set of strings which do not contain a substring ‘rt’ if ∑= {r, t}
1) (rt)*
2) (tr)*
3) (r*t*)
4) (t*r*)
Answer: 4
6) According to the precedence rules, x-y-z is equivalent to which of the following?
1) (x-y)-z
2) x-(y-z)
3) Both (x-y)-z and x-(y-z)
4) None of the mentioned
Answer: 1
7) Which among the following is not an associative operation?
1) Union
2) Concatenation
3) Dot
4) None of the mentioned
Answer: 4
8) Which among the following is equivalent to the given regular expression?01*+1
1) (01)*+1
2) 0((1)*+1)
3) (0(1)*)+1
4) ((0*1)1*)*
Answer: 3
9) According to the given transitions, which among the following are the epsilon closures of q1 for the given NFA?
Δ (q1, ε) = {q2, q3, q4}
Δ (q4, 1) =q1
Δ (q1, ε) =q1
1) q4
2) q2
3) q1
4) q1, q2, q3, q4
Answer: 4
10) 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.
1) True
2) False
Answer: 1
11) State true or false?
Statement: ε (Input) does not appears on Input tape.
1) True
2) False
Answer: 1
12) Statement 1: ε- transition can be called as hidden non-determinism.
Statement 2: δ (q, ε) = p means from q it can jump to p with a shift in read head.
Which among the following options is correct?
1) Statement 1 and 2, both are correct
2) Statement 1 and 2, both are wrong
3) Statement 1 is correct while Statement 2 is wrong
4) Statement 1 is wrong while Statement 2 is correct
Answer: 3
13) For NFA with ε-moves, which among the following is correct?
1) Δ: Q X (∑ U {ε}) -> P(Q)
2) Δ: Q X (∑) -> P(Q)
3) Δ: Q X (∑*) -> P(Q)
4) All of the mentioned
Answer: 1
14) Which among the following is false?ε-closure of a subset S of Q is:
1) Every element of S ϵ Q
2) For any q ϵ ε(S), every element of δ (q, ε) is in ε(S)
3) No other element is in ε(S)
4) None of the mentioned
Answer: 4
15) The automaton which allows transformation to a new state without consuming any input symbols:
1) NFA
2) DFA
3) NFA-e
4) All of the mentioned
Answer: 3
16) e-transitions are
1) conditional
2) unconditional
3) input dependent
4) none of the mentioned
Answer: 2
17) Under which of the following operation, NFA is not closed?
1) Negation
2) Kleene
3) Concatenation
4) None of the mentioned
Answer: 4
18) It is less complex to prove the closure properties over regular languages using
1) NFA
2) DFA
3) PDA
4) Can’t be said
Answer: 1
19) Which of the following is an application of Finite Automaton?
1) Compiler Design
2) Grammar Parsers
3) Text Search
4) All of the mentioned
Answer: 4
20) Which of the following do we use to form an NFA from a regular expression?
1) Subset Construction Method
2) Power Set Construction Method
3) Thompson Construction Method
4) Scott Construction Method
Answer: 3