Regular Languages and Model Theory 3: Constraint Systems and NFAs

In this video, I introduce the notion of a triangular constraint system, and a nondeterministic finite automaton.

Nondeterministic finite automata can alternately be thought of as deterministic finite automata but with randomness involved, where we say an NFA accepts if there is at least one timeline (at least one set of results of the randomness) in which it accepts. This perspective is perhaps better for thinking about multiple timelines in terms of our experience with NFAs than it is for thinking about NFAs in terms of our experience with multiple timelines.

If you have questions or something didn't make sense to you, please let me know in the comments below.

[alexandersanchez]

Cool video! I started out thinking, "what the heck are these triangles?" But then, I watched the whole thing and it was awesome.

[distrologic]

It is basically a graph structure, where the letters are the nodes and the numbers are the labels of the edges. Now there can be multiple edges with the same label for any letter, so its non-deterministic.

[identityelement]

These Triangular Constraint Systems are cool!!! I tried the simulation several times and it was fun. Especially when I got the word #ADAADA# with the solution They feel a bit like doing sudoku :)