An ELI5 version of REGEX and NFA

You have 🤖 a robot (our automaton) that will “walk” through the REGEX dungeon, room by room 🏚 (character by character). Now imagine each room is locked, and in order to access the next one it needs to collect from the string the key (or keys) character that unlocks the next REGEX door.

If the robot reaches the end of the REGEX, it’s free and it's a match!, if it gets stuck with a character that doesn’t open the next door it gets kicked to the start of the REGEX and needs to try again from the next string character. So if it has the string: "budega", and it fails at "b", it will try to open the REGEX again using "udega" (no matter how much progress it made on the previous dungeon).

If a robot is trying to match the dungeon /there/, it will need a set of keys that are able to unlock each of its 5 doors (t, h, e, r, e) in perfect succession:

• If I give it ”there”. It will ofc use all the keys and successfully reach the end.
• If I give it ”here” it never even starts, since it would never be able to unlock the first door. It would try "here", then "ere", then "re", then "e" and leave the dungeon feeling sad 🙁.
• If I give it ”then go over there” the robot would probably feel very confident going over the initial “the” only to get stuck with an “n” that can’t unlock the next door r and get kicked to try all over again with "hen go over there”. It would then successively fail in the first character until it got to try with "there”, and finally be happy again. 🎉

Some doors can be opened with a varying number of characters (quantifiers) or different ones (ranges).

A robot in the /[hm]el+ow?/ dungeon has 5 doors (characters) to cross: [hm], e, l+, o and w?.

• “hello” would be a match since the first door can be opened with either an "h" or an "m". And the l+ door would use both ls, leaving the robot with an “o” to use in the next door o. The last door w? can be opened with 0 or 1 valid keys. It has 0, so it gets through it.
• “mellow” also works for the same reasons above. At the last door w? it uses its 1 “w” and goes through it. Yay!

Anyway. I think I had way too much fun painting it in more vivid colors. I hope it helped.