Finite Automata in Computation Theory

Formal Definition of Computation

• A finite automaton M = (Q, Σ, δ, q0, F) accepts a string w = w1w2…wn if a sequence of states r0, r1, …, rn in Q exists with three conditions:
  • r0 = q0
  • δ(ri, wi+1) = ri+1, for i = 0, …, n-1
  • rn ∈ F
• M recognizes language A if A = {w | M accepts w}

Designing Finite Automata

• To design a finite automaton, determine the necessary information to remember about the input string as it is being read
• Represent this information as a finite list of possibilities
• Assign a state to each possibility
• Determine the transitions by seeing how to go from one possibility to another upon reading a symbol
• Set the start state to the state corresponding to the possibility associated with having seen 0 symbols so far
• Set the accept states to those corresponding to possibilities where you want to accept the input string

Example: Finite Automaton E1

• Designed to recognize the language of all strings with an odd number of 1s
• The possibilities are:
  • even so far
  • odd so far
• States are assigned to each possibility
• Transitions are set to flip state on a 1 and stay put on a 0
• Start state is qeven
• Accept state is qodd

Example: Finite Automaton E2

• Designed to recognize the regular language of all strings that contain the string 001 as a substring
• The possibilities are:
  • haven't just seen any symbols of the pattern
  • have just seen a 0
  • have just seen 00
  • have seen the entire pattern 001
• States are assigned to each possibility
• Transitions are set based on the possibilities and the input symbols
• Start state is q
• Accept state is q001

Regular Operations

• Three operations on languages are defined:
  • Union (A ∪ B)
  • Concatenation (A ∘ B)
  • Star operation (A*)
• The star operation is a unary operation that applies to a single language
• It works by attaching any number of strings in A together to get a string in the new language
• The empty string "" is always a member of A*, no matter what A is