Finite Automata (FA)

• A state diagram captures possible states and transitions a machine uses with input symbols
• Finite Automata are recognizers for Regular Languages

Finite Automata (FA) vs Other Computational Models

• FA differ from other models based on memory capabilities
• FA uses constant memory
• Pushdown automata and Turing Machines use varying memory
• FA is the most memory-restricted model
• FA is efficient at pattern recognition
• FA is unsuitable for complex computations needing variable memory

Uses of Finite Automata

• Lexical analysis (compilers)
• Pattern matching (e.g., regular expressions)
• Network protocol design
• Fundamental to understanding pushdown automata and Turing machines

Deterministic Finite Automaton (DFA)

• Consists of 5 elements:
• Q: finite set of states
• ∑: finite set of input symbols (alphabet)
• δ: transition function mapping Q x ∑ to Q
• q0: start state
• F: set of accepting states
• DFA is defined by the 5-tuple: {Q, ∑, δ, q0, F}
• Input a word (w) can be tested to see if it is acceptable by the DFA

DFA Steps

• Start at the start state q0
• Iterate through each input symbol in sequence w
• For each input in w calculate the next state from current state through transition function
• If the final state is in the set of accepting states (F), accept w, otherwise, reject w.

Constructing a DFA

• Crucial to identify what info is needed to remember from the input string as it is read
• Represent the information needed as a finite list of possibilities
• Assign a state to each of the possibilities
• Assign transitions to show how to go from each possibility to another when reading a symbol
• Set the start state to correspond with having seen 0 symbols so far or the empty string ɛ
• Set accept states to coincide with where the input string is accepted

Formal Description of a Finite Automaton

• Q is a finite set called the states
• ∑ is a finite set called the alphabet
• δ: Q × ∑ --> Q is the transition function, which maps to a single state
• q0 ∈ Q is the start state
• F ⊆ Q is the set of accept states

Visual Representation

• Finite automaton called M1 is depicted using the state diagram
• State diagram illustrates the states of M1 labeled q1, q2 & q3
• The start state, q1, comes from the arrow pointing at it
• Accept state is marked by a double circle
• Transitions are represented by arrows

DFA Processing

• Processes an input string (like 1101) and produces an output, accepting or rejecting
• Begins in M1’s start state, receiving symbols from left to right
• After each symbol, the automaton transitions based on the symbol's label
• Output is produced after reading the last symbol; accept if in an accept state, otherwise reject

Formal Language and Representation

• If A is the set of accepted strings and M accepts it, A is the language of machine M, write L(M) = A
• M recognizes A
• Machines may accept strings, but only recognize one language
• Accepting no strings still recognizes the empty language Ø

Regular Languages

• L(A) defines a language recognized by DFA A
• L(A) is a "Regular Language”
• Can be expressed in the Chomsky Hierarchy

Defining Regular Languages

• Finite automata can accept family of languages = regular languages
• Language L is regular if and only if there is a DFA that accepts L
• Construct a DFA to accept L
• Regular languages are applicable in input string scanning to find patterns
• L = {(ab)na, n > 0} is regular

Transition Table Steps

• Build a DFA for L = {w | w is a binary string that contains 01 as a substring}
• ∑ = {0,1}
• Decide on Q, states
• Designate start and final state(s)
• δ can decide on transitions
• "Final” states == "accepting states”
• Other states == "non-accepting states”

Regular Operations

• Arithmetic uses numbers with + and × to manipulate them
• Computation theory uses languages and operations for manipulating them
• Regular operations are: union, concatenation, and star

Regular Operations - Definitions

• Union: A ∪ B = {x | x ∈ A or x ∈ B}
• Concatenation: A o B = {xy | x ∈ A and y ∈ B}
• Star: A* = {x1x2...xk | k ≥ 0 and each xi ∈ A}

Regular Operation Example

• ∑ = {a, b, . . . , z}, A = {good, bad}, B = {boy, girl}
• A ∪ B = {good, bad, boy, girl}
• A o B = {goodboy, goodgirl, badboy, badgirl}
• A* = {ε, good, bad, goodgood, goodbad, badgood, badbad, goodgoodgood, goodgoodbad, goodbadgood, goodbadbad, . . .}

Regular Operations: Closure Under Union

• Regular languages are closed under the union operation
• If A₁ and A2 are regular languages, then A1 ∪ A2 is regular
• Proof by construction is used to show that A_1 ∪ A_2 is regular

Constructing M

• Construction uses languages A1 and A2 with finite automaton M1 recognizing A1 and M2 recognizing A2
• Proof needs to demonstrate a finite automaton called M that recognizes A1 ∪ A2

One Idea

• Simulate M1 on the input and then simulate M2 on the input
• Once symbols of the input have been read and M1 is not accepted, the simulation tries M2
• Is not possible in a FA, it cannot “rewind the input tape” on M2

Closure Under Union

• Can keep track of machine states in parallel to simulate M1 and M2 simultaneously as input arrives
• One pass through the input
• Track the state of each machine at each point, needing finite memory
• Remember a pair of states: one from M1 and one from M2
• If M1 has k1 states & M2 has k2 states, number of state pairs is k1 × k2
• The total number of states in the combined machine M is k1 × k2, corresponding to each state pair
• Transitions in M occur between state pairs, updating both M1 and M2's states
• Accept states M are pairs with either M1 or M2 in an accept state

Formal Proof of Closure Under Union

• M1 recognizes A1, where M1 = (Q1, ∑, δ1, q1, F1) & M2 recognizes A2, where M2 = (Q2, ∑, δ2, q2, F2)
• Construct M to recognize A1 ∪ A2, where M = (Q, ∑, δ, q0, F)
• Q = {(r1, r2)| r1 ∈ Q1 and r2 ∈ Q2}
• The set is the Cartesian product of sets Q1 and Q2 written as Q1 × Q2, as the set of all pairs, first from Q1 and second from Q2
• Σ, the alphabet, is the same as in M1 & M2
• For simplicity, both M1 & M2 have same input Σ
• Theorem remains true for different alphabets, Σ1 & Σ2, modifying the proof with Σ = Σ1 ∪ Σ2
• δ, transition, is defined as follows, where (r1, r2) ∈ Q and each a ∈ Σ: δ((r1, r2), a) = (δ1(r1, a), δ2(r2, a))
• δ gets a state of M, a pair of states from M1 & M2, an input symbol and returns M's next state
• q0 is the pair (q1, q2)
• F is the set of pairs with members of M1 or M2 as accept states, written as: F = {(r1, r2)| r1 ∈ F1 or r2 ∈ F2}
• The expression is the same as F = (F1 × Q2) ∪ (Q1 × F2) and not F = F1 × F2

Concatenation

• The class of regular languages is closed under the concatenation operation
• For regular languages A1 & A2, A1 o A2 is regular
• Nondeterminism is needed to prove this