Home › GATE CSE › computerscience › Theory of Computation › A DFA accepts an input string $w$ if and only if
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)._
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?