Practice free →
HomeGATE CSEcomputerscienceTheory of Computation › An $\varepsilon$-TRANSITION in an NFA allows the…

An $\varepsilon$-TRANSITION in an NFA allows the automaton to

Askip an arbitrary number of symbols in the input
Bhalt the computation early
Cconsume any symbol from the alphabet
Dmove from one state to another WITHOUT consuming any input symbol
Answer & Solution
Correct answer: D. move from one state to another WITHOUT consuming any input symbol
1. NFAs can have $\varepsilon$-transitions: $\delta(q, \varepsilon)$ — moves from state $q$ to another state(s) WITHOUT reading any input. 2. These allow the automaton to take 'free' moves between states, useful for building larger NFAs from smaller ones (e.g. for union, concatenation, star). 3. The $\varepsilon$-closure of a state $q$ is the set of all states reachable from $q$ using zero or more $\varepsilon$-transitions. 4. NFAs with $\varepsilon$ are equivalent in power to those without (and to DFAs). 5. Options A, C, D mischaracterise $\varepsilon$-moves. _Source: Jeff Erickson, "Models of Computation", §2.7 ($\varepsilon$-transitions)._
Solve this in the app — GATE CSE practice & 24k+ MCQs →
Related questions