alleryStart learning →A DFA accepts an input string $w$ if and only if
Athe computation visits every state at least once
Bthe input contains an even number of zeroes
Cthe computation halts before reading all of $w$
Dcomputation ends in an accepting state
Answer & Solution
Correct answer: D. computation ends in an accepting state
1. A DFA's computation on input $w = w_1 w_2 \ldots w_n$:
- Start in $q_0$
- For each symbol $w_i$, transition: $q_{i} = \delta(q_{i-1}, w_i)$
- End in state $q_n$ after reading all symbols
2. ACCEPTANCE: the DFA accepts $w$ iff $q_n \in F$.
3. The LANGUAGE of $M$ is $L(M) = \{w \mid M \text{ accepts } w\}$. Languages recognised by DFAs are precisely the REGULAR LANGUAGES.
4. Options A, C, D are wrong or unrelated criteria for acceptance.
_Source: Jeff Erickson, "Models of Computation", §2.4 (Acceptance condition)._
Keep practising Theory of Computation
Browse all Theory of Computation questions for GATE CSE, or explore more Computer Science topics.
Related questions
Which class of grammars generates ALL recursively enumerable languages?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$ isContext-free languages are RECOGNISED by which type of machine?A CFG is AMBIGUOUS ifConsider the CFG with rule $S \to aSb \mid \varepsilon$. The language generated is