Question bank — NFA — formal definition, epsilon transitions

False. Both recognise exactly the regular languages; subset construction turns any NFA into an equivalent DFA. NFAs save design effort, not raise power.

True. Rejection means no surviving path reaches $F$; if all paths die, none can be final, so $\hat{\delta }(q_0,w)\cap F=\varnothing$.

False. $\epsilon \notin \Sigma$ always. It appears only in $\delta$'s domain as $\Sigma \cup \{\epsilon \}$; no input string ever contains an $\epsilon$ symbol.

False. The set can have size one (or zero). The machinery allows many states; whether it actually holds many depends on the transitions taken.

True. $\hat{\delta }(q_0,\epsilon )=\text{ECLOSE}(q_0)$, so $\epsilon \in L(N)$ exactly when that closure contains a final state.

False. $\delta (q,a)=\varnothing$ just kills that branch; sibling branches continue. Empty $\ne$ error, unlike a DFA where a missing edge is genuinely undefined.

True. Wrap each DFA target state in a singleton set and use no ε-moves; then $\delta :Q\times \Sigma \to \mathcal{P}(Q)$ with all outputs of size one — a legal NFA.

True. With zero ε-arrows the only state reachable "for free" from $q$ is $q$, so $\text{ECLOSE}(S)=S$ and the closure step becomes a no-op.

False. It lands in a set; acceptance needs just one member of that set to be in $F$. Uniqueness is irrelevant.

True. Enlarging $F$ can only make more intersections $\hat{\delta }(q_0,w)\cap F$ non-empty; no previously accepted string is lost.

Missing the ε-closure. The correct step is $\text{ECLOSE}({\bigcup }_r\delta (r,a))$; skipping it can drop states reachable for free after reading $a$ and wrongly reject.

Wrong. $\text{ECLOSE}(q)$ always contains $q$, but $\delta (q,\epsilon )$ (a single one-step move) may be $\varnothing$ or point to other states. Don't confuse the one-step ε-transition with the closure.

Should be $\hat{\delta }(q_0,w)\cap F\ne \varnothing$. The $\subseteq$ version demands all reached states be final (universal); NFA acceptance is existential — one is enough.

The domain is incomplete — it must be $Q\times (\Sigma \cup \{\epsilon \})$. Without $\epsilon$ in the domain there are no free moves, so this is only an NFA-without-ε.

Wrong — it is zero or more ε-moves, and it includes $q$ itself. You can chain ε-arrows arbitrarily and you can also stay put.

A dead branch is ignored, not fatal. As long as another branch survives to a final state, the string is accepted. One death does not sink the ship.

No — $\mathcal{P}(Q)$ is the power set: the set of all subsets of $Q$. That is precisely what lets $\delta$ output "many/zero states."

Because "zero ε-moves" is a valid choice — you can always stay where you are for free — so $q$ is trivially reachable from $q$.

A DFA state can encode a whole subset of NFA states (subset construction), tracking every branch at once. The flexibility is bought back by using exponentially more DFA states, not extra power.

Returning a set is exactly what encodes nondeterminism: multiple targets (size $>1$), a dead branch (size $0$), or a deterministic move (size $1$) all become one uniform "set of next states."

A newly entered state may sit at the tail of an ε-arrow leading into a final state; failing to slide there for free would miss an accepting path and wrongly reject.

A fresh start state with ε-arrows into both machines lets the NFA "guess" which branch to take before reading anything, wiring two automata into one without touching their alphabets.

Because the string is in $L(N)$ iff there exists at least one path through the choices ending in $F$. It mirrors the logical $\exists$, not $\forall$.

The operators (union, concatenation, star) map to ε-glue between small sub-NFAs; nondeterminism absorbs the "which alternative?" choices that a DFA would have to resolve up front.

The empty language $\varnothing$. No state is accepting, so $\hat{\delta }(q_0,w)\cap F=\varnothing$ for every $w$ — nothing is ever accepted.

Yes. $\text{ECLOSE}(q_0)=\{q_0,q_1\}$ contains $q_0\in F$, so $\epsilon$ is accepted regardless of $q_1$'s status.

No. ECLOSE collects a set; once $q$ and $q^{\prime }$ are both in, revisiting adds nothing new and the computation terminates. It's a reachable-set, not a path enumeration.

Every branch dies the moment $a$ is read, so the reached set becomes $\varnothing$ and stays empty — the string is rejected (no path survives).

Only $\epsilon$ itself. With no way to consume an input symbol, any non-empty string dies immediately; acceptance is possible only when the input is empty and ECLOSE of the start hits $F$.

$\varnothing$. On any input beyond the start there is nowhere to go, and $\epsilon$ fails too since $q_0\notin F$ and its closure is just $\{q_0\}$.

No. Once the reached set is $\varnothing$, ${\bigcup }_{r\in \varnothing }\delta (r,a)=\varnothing$ for all remaining symbols — an empty set is absorbing, the computation is dead for good.