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.

Learn about finite automata, regular operations such as union, concatenation, and star closure, and how they are used to recognize patterns in strings.