DeterministicFiniteAutomata.md (1197B)
1 # Deterministic Finite Automaton (DFA) 2 3 **Source:** Theory of Computation 4 5 **Lecture:** 2 6 7 **Definition:** A deterministic finite automaton is a 5-tuple (Q, Sigma, delta, q_0, F) where each coordinate represents the following: 8 9 1. Q - Finite **set** of states. 10 2. Sigma - Finite alphabet. 11 3. delta - This is a function from Q x Sigma -> Q. As such, this represents state transitions, referred to as the transition function. 12 4. q_0 - Initial state (q_0 \in Q) 13 5. F - Set of final state(s) (F is a subset of Q) 14 15 Note: A DFA **must** contain state transitions for each member of the alphabet for each state. 16 17 ### Representation 18 19 Often these are represented as a directed labeled graph (transition diagram). 20 21 When creating these accepting states (final states) have a concentric circle in their node (double circles as prof. referred to it) and the start state (only 1) has an arrow leading in from nowhere. 22 23 ### Language 24 25 The language of a DFA is the set of all strings that M, defined as the machine, accepts. For M to accept a word there must be a sequence of states transitions that ends in an accepting state and starts at the initial state. We say L is the language of M and can state L = L(M).