Home › GATE CSE › computerscience › Theory of Computation › A DETERMINISTIC FINITE AUTOMATON (DFA) is a 5-tu…
A DETERMINISTIC FINITE AUTOMATON (DFA) is a 5-tuple $M = (Q, \Sigma, \delta, q_0, F)$. Which component represents the TRANSITION FUNCTION?
A$Q$, the finite set of states
B$\Sigma$, the input alphabet
C$\delta : Q \times \Sigma \to Q$
D$F \subseteq Q$, the accept states
Answer & Solution
Correct answer: C. $\delta : Q \times \Sigma \to Q$
1. A DFA's transition function $\delta$ takes a (state, symbol) pair and returns the NEXT state. So $\delta : Q \times \Sigma \to Q$.
2. KEY property of DFA: $\delta$ is TOTAL (defined for every state-symbol pair) and DETERMINISTIC (returns exactly one next state).
3. Components of the 5-tuple:
- $Q$: finite set of states
- $\Sigma$: input alphabet (finite)
- $\delta$: transition function (option C)
- $q_0 \in Q$: start state
- $F \subseteq Q$: accepting (final) states
4. Other options name different components.
_Source: Jeff Erickson, "Models of Computation", §2.4 (Finite-State Automata)._
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?