← CSC 313 Theory of Computation
Deterministic Finite Automata and Regular Languages
Notes
Introduction to Finite Automata
In theoretical computer science, finite automata are abstract computational models designed to recognize patterns within input strings over a specified alphabet. A Deterministic Finite Automaton (DFA) represents the most fundamental computational machine with finite memory. The machine processes input symbols strictly one at a time, moving deterministically from state to state according to a fixed transition function. Because DFAs cannot remember past inputs beyond what their current state captures, they recognize only the simplest class of formal languages, termed regular languages.
Formal Definition of a DFA
A DFA is mathematically formalized as a five-tuple consisting of Q, Sigma, delta, q0, and F. Q is a finite set of internal states. Sigma represents the finite input alphabet. Delta is the transition mapping function that takes an existing state and an input symbol to output a single unique subsequent state. Symbol q0 designates the unique start state from which computation begins. F constitutes the set of accepting or final states. If after consuming the entire input sequence the automaton halts in any state belonging to F, the input string is formally accepted; otherwise, it is rejected.
Practical example
Consider an automated USSD verification module designed for Kenya commercial telecom networks such as Safaricom. The system validates whether a dialed customer session follows the syntax for launching the M-Pesa menu. The protocol requires all valid strings to start with an asterisk, followed immediately by three, three, four, and terminated by a hash symbol. Intermediate digits are allowed only if separated by asterisks for service sub-menus.
Alphabet Sigma contains the asterisk, hash, and numeric digits zero through nine.
State q0 is the start state. When the user dials an asterisk, delta transitions from q0 to state q1.
From state q1, the system reads digit 3 to enter state q2.
From state q2, reading another 3 leads to state q3.
From state q3, reading digit 4 leads to state q4. State q4 denotes that 334 has been successfully dialed.
From state q4, if the input is a hash symbol, the machine transitions to state q_accept, which belongs to F.
If from state q4 an asterisk is received, it transitions to state q_sub to collect sub-menu parameters. Any invalid sequence, such as receiving a letter, premature hash, or incorrect sequence like star three two one, directs the automaton into state q_dead, which has no escape transitions to accepting states.
Because each state and input pair yields exactly one transition, the telecom switch deterministically filters out corrupt USSD packets before dedicating core gateway server resources.
Quiz
1. Which component of the formal five-tuple defines the initial starting point of a Deterministic Finite Automaton?
2. In the M-Pesa USSD example, what purpose does the dead state serve?
3. What class of formal languages is strictly recognized by Deterministic Finite Automata?
Sign in to submit and securely grade your quiz.