you are in a maze of twisty little passages

you ain't gonna need it

beep boop

twisty little passages, all different

twisty little passages, all alike

twisty little passages, kinda similar

twisty little passages, kinda similar

You are at the entrance

You are at the entrance
>> left
You are in a passage

You are at the entrance
>> left
You are in a passage
>> left
You are at the entrance

You are at the entrance
>> left
You are in a passage
>> left
You are at the entrance
>> right
You are in a passage

You are at the entrance
>> left
You are in a passage
>> left
You are at the entrance
>> right
You are in a passage
>> left
You are in a passage

You are at the entrance
>> left
You are in a passage
>> left
You are at the entrance
>> right
You are in a passage
>> left
You are in a passage

You are at the entrance
>> left
You are in a passage
>> left
You are at the entrance
>> right
You are in a passage
>> left
You are in a passage

"" "L"
E P
P E
P P
NAME "" "L"
"" E P
"L" P E
"R" P P
NAME "" "L"
"" E E
"R" P E
"RR" P P
"RRR" P P
NAME "" "L" "LL"
"" E E E
"R" P E E
"RR" P P E
"RRR" P P P
NAME "" "L" "R"
"" E P P
"L" P E E
"R" P E E
NAME "" "L" "LL"
"" E E E
"R" P E E
"RR" P P E
"RRR" P P P
NAME "" "L" "LL"
"" E E E
"R" P E E
"RR" P P E
"RRR" P P P
NAME EXIT "" "L" "LL"
"" L E E E
"R" L E E E
"RR" L P E E
"RRR" L P P E
"RRR" R P P P
NAME "" "L" "LL"
"" E E E
"R" P E E
"RR" P P E
"RRR" P P P
NAME EXIT "" "L" "LL" DESTINATION
"" L E E E ""
"R" L E E E ""
"RR" L P E E "R"
"RRR" L P P E"RR"
"RRR" R P P P"RRR"

how do we find experiments?

by learning from mistakes!

You are at the entrance

You are at the entrance
>> right
You are in a passage

You are at the entrance
>> right
You are in a passage
>> right
You are in a passage

You are at the entrance
>> right
You are in a passage
>> right
You are in a passage
>> right
You are in a passage

You are at the entrance
>> right
You are in a passage
>> right
You are in a passage
>> right
You are in a passage
>> left
You are in a passage

You are at the entrance
>> right
You are in a passage
>> right
You are in a passage
>> right
You are in a passage
>> left
You are in a passage
>> left
You are in a passage

You are at the entrance
>> right
You are in a passage
>> right
You are in a passage
>> right
You are in a passage
>> left
You are in a passage
>> left
You are in a passage

ROOMRESTRESULT
"""RRRLL" P
ROOMRESTRESULT
"""RRRLL" P
"R""RRLL" P
ROOMRESTRESULT
"""RRRLL" P
"R""RRLL" P
"RR""RLL" P
ROOMRESTRESULT
"""RRRLL" P
"R""RRLL" P
"RR""RLL" P
"RR""LL" E
ROOMRESTRESULT
"""RRRLL" P
"R""RRLL" P
"RR""RLL" P
"RR""LL" E
"R""L" E
ROOMRESTRESULT
"""RRRLL" P
"R""RRLL" P
"RR""RLL" P
"RR""LL" E
"R""L" E
"""" E
NAME ""
"" "E"
"L" "P"
ROOMRESTRESULT
"" "RR" P
"L" "R" E
"" "" E
NAME "" "R"
"" "E" "P"
"L" "P" "E"
"R" "P" "P"
ROOMRESTRESULT
"" "LLLLR" T
"L" "LLLR" T
"R" "LLR" P
"R" "LR" P
"R" "R" P
"L" "" P
NAME "" "R" "LLR"
"" "E" "P" "P"
"L" "P" "E" "P"
"R" "P" "P" "P"
"LL" "P" "P" "T"
ROOMRESTRESULT
"" "LLLLR" T
"L" "LLLR" T
"LL" "LLR" T
"R" "LR" P
"R" "R" P
"L" "" P
NAME "" "R" "LLR" "LR"
"" "E" "P" "P" "E"
"L" "P" "E" "P" "P"
"R" "P" "P" "P" "P"
"LL" "P" "P" "T" "P"
"LLL" "P" "P" "P" "T"
"LLLL" "P" "T" "P" "P"
"LLLLR" "T" "E" "P" "E"

RECAP

  1. Descriptions distinguish rooms.
  2. Use paths as experiments to distinguish more.
  3. These let us build a map.
  4. When our map is wrong, we learn a new experiment!

why?

Further Reading

Learning regular sets from queries and counterexamples
Angluin, Dana.

Inference of finite automata using homing sequences
Rivest, Ronald L. and Robert E. Schapire.

L* Search and Inference of Deterministic Finite Automata
David R. MacIver (me)