CSCE 222 Lecture 29

« previous | Friday, April 15, 2011 | next »

Finite State Automata

Given by 5-tuple: $M=(S,I,s,s_{0},F)$

• $S$ is a set of states
• $I$ is the input alphabet
• $f$ is a transition function mapping one state to another based on the input
• $s_{0}$ is the starting state (s₀ ∈ S)
• $F$ is a set of the accepting states (F ⊆ S) that we're supposed to end on

Recognize strings that end in "–ing"

States:

• Start (0)
• Saw "i" (1)
• Saw "in" (2)
• Saw "ing" (3)

Functions:

• (0|1|2|3) + "i" → (1)
• (1) + "n" → (2)
• (2) + "g" → (3)
• (1|2|3|) + anything not matching → (0)

Representing this in code: Make a piece of code for each state that

1. reads the next input
2. decides the next state
3. jumps to the beginning of the code for that state

void start() {
  char c = getNextInput();
  if (c == 'i') sawI();
  else start()
}

void sawI() {
  char c = getNextInput();
  if (c == 'n') sawIN();
  else if (c == 'i') sawI();
  else start();
}

void sawIN() {
  char c = getNextInput();
  if (c == "g") sawING();
  else start();
}

void sawING() {
  char c = getNextInput();
  if (c) start();
}

Footnotes

Read Design Patterns: Elements of Reusable Object-Oriented Software by the Gang of Four