Home › GATE CSE › computerscience › Theory 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)._
Related questions
Which class of grammars generates ALL recursively enumerable languages?What is a LEFTMOST DERIVATION?Which of the following languages is CONTEXT-FREE?Consider the grammar $S \to (S) \mid SS \mid \varepsilon$. The language generated isEvery regular language is also context-free. The PROOF construction isThe CYK algorithm parses a CFG in CNF. Its time complexity for a string of length $n$ isA LEFT-RECURSIVE rule in a CFG has the form $A \to A\alpha$ for some non-empty $\alpha$. WContext-free languages are CLOSED under which of the following operations?