Finite State Automata (FSAs)

• Finite State Automta are a basic computer language precept.
• Chomsky notes it's equivalent to regular languages.
• You can readily implement FSAs with binary CAs.
• FSAs are composed of states and they can recognise (or generate) instances of a language. (They're also used to simulate a lot of games agents like Mario in Mario Kart. They're also used as the first bit of compilers (via for instance YACC)).
• They're not quite Turing complete, but they go a long way to manage processing.
• They're is one active state, a start state, and a final state.
• There is an alphabet of inputs.
• When an input is presented, the FSA may move from one state to another. It's a directed graph with parts of the alphabet on the arcs.
• If the FSA ends on a final state then the input is a string (of inputs from the alphabet) in the language. If not, the string is not in the language.
• There's a lot more of formal language and automata theory, but these are the basics of FSAs.