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.