Finite Automata and Regular Operations

Finite Automata

• A finite automaton is a simple machine that can recognize patterns in strings.
• Four possibilities to assign states: haven't seen any symbols of the pattern, seen a 0, seen 00, or seen the entire pattern 001.
• Transitions are assigned based on reading a 1 or a 0.

Regular Operations

• Three operations on languages: union, concatenation, and star (closure).
• Union: combines strings from two languages into one language.
• Concatenation: attaches strings from two languages in all possible ways.
• Star operation: applies to a single language, attaches any number of strings together; the empty string is always a member of A*.

Example 1.24

• A = {good, bad} and B = {boy, girl}, then
  • A U B = {good, bad, boy, girl}
  • A ∩ B = {goodboy, goodgirl, badboy, badgirl}
  • A* = {", good, bad, goodgood, goodbad, badgood, badbad, ...}

Designing Finite Automata

• Determine what information to remember about the string as it is being read.
• Represent this information as a finite list of possibilities.
• Assign a state to each possibility.
• Assign transitions based on reading a symbol.

Example 1.21

• Design a finite automaton E2 to recognize the regular language of all strings that contain the string 001 as a substring.
• Initially skip over all 1s, then note that a 0 may be the first symbol of the pattern 001.
• If a 1 is seen, go back to skipping over 1s; if a 0 is seen, remember two symbols of the pattern and continue scanning for a 1.

Formal Definition of Computation

• A finite automaton M = (Q, Σ, δ, q0, F) accepts a string w if a sequence of states r0, r1, ..., rn in Q exists with three conditions:
  • r0 = q0 (starts in the start state)
  • δ(ri, wi+1) = ri+1 (machine goes from state to state according to the transition function)
  • rn ∈ F (machine accepts its input if it ends up in an accept state)

Designing Finite Automata (continued)

• To design a finite automaton E1 to recognize the language of all strings with an odd number of 1s:
  • Remember whether the number of 1s seen so far is even or odd.
  • Flip the answer if a 1 is read, leave the answer as is if a 0 is read.
  • Assign states and transitions based on this information.