Answer:
Formal Definition
A deterministic finite automaton (DFA) is a finite state machine that accepts or rejects a given string of symbols, by running through a state sequence uniquely determined by the string. Deterministic refers to the uniqueness of the computation run.
Here is the formal definition of the DFA including the transition table:
- Q:The set of states is {q0, q1, q2}.
- Σ:The set of input symbols is {0, 1}.
- δ: The transition function is δ(q, σ) = q',
where q is the current state, σ is the input symbol, and q' is the next state. The transition function is defined as follows:
- δ(q0, 0) = q1
- δ(q0, 1) = q2
- δ(q1, 0) = q2
- δ(q1, 1) = q0
- δ(q2, 0) = q0
- δ(q2, 1) = q1
q0: The initial state is q0.
F: The set of accepting states is {q1}.
The DFA accepts the strings that start with 0 and end with 1. For example, the strings 01, 001, and 0001 are all accepted by the DFA. strings 1, 10, and 11 are not accepted by the DFA.