Finite State Automata

Teaching educators
Suitable

Preview slides with notes

We recommend previewing these slides on a larger screen to view the slides and speaker notes easily.

Finite State Automata

Key questions

  • Have you heard of an automaton?
  • What kinds of things can "state" refer to?
  • What does "finite" mean?

Trainsylvania

Sequences

Did we get it right?

Map of Trainsylvania

Trainsylvania Questions

  1. BBB will take us to East Station
  2. BABA will take us to back to Airport Station
  3. Will AAB get us to Harbour Station? No
  4. Will ABBAB get us to Harbour Station? Yes
  5. Will AAABBAB get us to Harbour Station? Yes
  6. Will BBBBB get us to Harbour Station? No

What is it all about?

Is this English?

  1. Tim likes cake.
  2. ADM;lasdf oodf9 bosfa
  3. ancay youay eakspay igpay atinlay?

Finite State Automata

Map for email addresses

me@a.com

Finite State Automata

Map for email addresses

email@gmail.com

Finite State Automata

Map for email addresses

mygooglegmail

Finite State Automata

Additional challenges

  • Can you find another sequence, perhaps a longer one?
  • Suppose you wanted to take a really long route... can you find a sequence of 12 hops that would get you there? 20 hops?

Finite State Automata

Treasure Island version

Supporting Resources