Welcome to Finite States!

A puzzle game about solving simple problems with different types of models of computation. Before we begin, how familiar are you with models of computation from theoretical computer science. 0 Being no knowledge and 10 being an expert.

Finite States Help

Close

Note If you ever run into a bug, refresh the page to reload the current level.

Basic Controls

• Double click to create a new state
• Double click a state to mark it as accept, double click it again to mark it a normal state
• Shift+click from one state to a second state to create a transition, the second state can be the same as the first
• Click on a transition to edit its symbol matching options

Deterministic Finite Automata (DFA)

DFAs are the simplest type of automata, they do not have branches or epsilon (empty symbol) transitions. When pressing step, the next symbol will be read from the right side table and the current state will test all outgoing branches if any match. The starting state will always be S₀.

Formally a DFA must have a branch for every possible input it could receive, however in Finite States, this is not needed, assume if a symbol is not matched by any branch the DFA transitions to a reject state.

NonDeterministic Finite Automata (NFA)

NFAs have the power to 'guess' by matching 1 symbol against many different branches. NFAs also have the epsilon transition which matches the empty symbol. An epsilon transition will always be followed no matter what and will not consume any input. Although NFAs have these additional properties, they are only as powerful as DFAs and in fact, any NFA can be represented as a DFA.

For example the above NFA is a good way of trying out two paths before reading any input, if you know your result can be found in 2 branches, you can nondeterminstically try them both and see which accepts.

If one branch accepts, the entire NFA will accept the input, as long as there are other branches to run, if a branch rejects the NFA will continue. If all branches reject then the NFA will reject the input.

Pushdown automata (PD)

PDs are the first automata to have external memory, called the stack. Pushing a symbol will add it to the top and poping a symbol will remove to topmost element. If the stack is empty, poping will do nothing. PDs have the ability to match what to pop, for example the transition a : ← b indicates on input symbol a and if the top of the stack is a b pop a b. If the stack comparison fails, the transition is not taken. When pushing an element the stack is not compared to. Remember you still have the power of nondeterminism and DFAs, by setting the output to blank, the transition will act like on in a NFA or DFA.

Checking if the stack is empty

By default PDs do not have a method of checking if the stack is empty, one way to do this is to designate a special symbol as the bottom of the stack, once that symbol is removed you know the stack is empty. Here is an example

Before reading any input, the above PD pushes a $ onto the stack, it then moves to S₁ which at every step nondeterminstically does some work and also checks if the stack is empty by branching to S₃ and trying to push the special symbol off. If it does, then it accepts otherwise the branch rejects and we try again next step.

Turing Machine(TM)

The TM is the most powerful model of computation and has an infinite amount of external memory. It has a tape head which can read and write to from its current position and can be moved left or right.

At each step, the TM must move either left or right, by default it will move left. The second textbox is the symbol to write to that tape cell, in general the syntax for a transition a : b → L which means on reading the symbol a , write a b over the current cell, and then move left.

The default symbol on the tape is the blank symbol, represented by an underscore ( _ ). If you leave the second textarea blank, the TM will not write to the current cell, this is just short hand for x : x → L/R

Close