1. The total number of states to build the given language using DFA:
L = {w | w has exactly 2 a’s and at least 2 b’s}
a) 10
b) 11
c) 12
d) 13
Explanation: We need to make the number of a as fixed i.e. 2 and b can be 2 or more. Thus, using this condition a finite automata can be created using 1 states.
2. 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
a) q4
b) q2
c) q1
d) q1, q2, q3, q4
Explanation: The set of states which can be reached from q using ε-transitions, is called the ε-closure over state q.
3. An NFA can be modified to allow transition without input alphabets, along with one or more transitions on input symbols.
a) True
b) False
Explanation: It is possible to construct an NFA with ε-transitions, presence of no input symbols, and that is called NFA with ε-moves.
4. ε (Input) does not appears on Input tape.
a) True
b) False
Explanation: ε does not appears on Input tape, ε transition means a transition without scanning a symbol i.e. without moving the read head.
5. 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?
a) Statement 1 and 2, both are correct
b) Statement 1 and 2, both are wrong
c) Statement 1 is correct while Statement 2 is wrong
d) Statement 1 is wrong while Statement 2 is correct
Explanation: The transition with ε leads to a jump but without any shift in read head. Further, the method can be called one to introduce hidden non-determinism.
6. For NFA with ε-moves, which among the following is correct?
a) Δ: Q X (∑ U {ε}) -> P(Q)
b) Δ: Q X (∑) -> P(Q)
c) Δ: Q X (∑*) -> P(Q)
d) All of the mentioned
Explanation: Due to the presence of ε symbol, or rather an epsilon-move, the input alphabets unites with it to form a set including ε.
7. The __________ of a set of states, P, of an NFA is defined as the set of states reachable from any state in P following e-transitions.
a) e-closure
b) e-pack
c) Q in the tuple
d) None of the mentioned
Explanation: The e-closure of a set of states, P, of an NFA is defined as the set of states reachable from any state in P following e-transitions.
8. Which among the following is false?
ε-closure of a subset S of Q is:
a) Every element of S ϵ Q
b) For any q ϵ ε(S), every element of δ (q, ε) is in ε(S)
c) No other element is in ε(S)
d) None of the mentioned
Explanation: All the mentioned are the closure properties of ε and encircles all the elements if it satisfies the following options:
a) Every element of S ϵ Q
b) For any q ϵ ε(S), every element of δ (q, ε) is in ε(S)
c) No other element is in ε(S)
9. The automaton which allows transformation to a new state without consuming any input symbols:
a) NFA
b) DFA
c) NFA-l
d) All of the mentioned
Explanation: NFA-l or e-NFA is an extension of Non deterministic Finite Automata which are usually called NFA with epsilon moves or lambda transitions.
10. e-transitions are
a) conditional
b) unconditional
c) input dependent
d) none of the mentioned
Explanation: An epsilon move is a transition from one state to another that doesnt require any specific condition.