Presentation controls

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

Question 1

BBB will take us to East Station

Question 2

BABA will take us to back to Airport Station

Question 3

Will AAB get us to Harbour Station? No

Question 4

Will ABBAB get us to Harbour Station? Yes

Question 5

Will AAABBAB get us to Harbour Station? Yes

Question 6

Will BBBBB get us to Harbour Station? No

What is it all about?

Is this English?

  1. I'm gonna be late
  2. ADM;lasdf oodf9 bosfa
  3. ancay youay eakspay igpay atinlay?

Email address to process

me@a.com

Email address to process

email@gmail.com

Email address to process

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