Finite State Machines

A finite state machine (sometimes called a finite state automaton) is a computation model that can be implemented with hardware or software and can be used to simulate sequential logic and some computer programs. Finite state automata generate regular languages. Finite state machines can be used to model problems in many fields including mathematics, artificial intelligence, games, and linguistics.

A system where particular inputs cause particular changes in state can be represented using finite state machines. This example describes the various states of a turnstile. Inserting a coin into a turnstile will unlock it, and after the turnstile has been pushed, it locks again. Inserting a coin into an unlocked turnstile, or pushing against a locked turnstile will not change its state.

There are two types of finite state machines (FSMs): deterministic finite state machines, often called deterministic finite automata, and non-deterministic finite state machines, often called non-deterministic finite automata. There are slight variations in ways that state machines are represented visually, but the ideas behind them stem from the same computational ideas. By definition, deterministic finite automata recognize, or accept, regular languages, and a language is regular if a deterministic finite automaton accepts it. FSMs are usually taught using languages made up of binary strings that follow a particular pattern. Both regular and non-regular languages can be made out of binary strings. An example of a binary string language is: the language of all strings that have a 0 as the first character. In this language, 001, 010, 0, and 01111 are valid strings (along with many others), but strings like 111, 10000, 1, and 11001100 (along with many others) are not in this language.

You can walk through the finite state machine diagram to see what kinds of strings the machine will produce, or you can feed it a given input string and verify whether or not there exists a set of transitions you can take to make the string (ending in an accepting state).

Deterministic Finite Automata

A deterministic finite automaton (DFA) is described by a five-element tuple: $(Q, \Sigma, \delta, q_0, F)$.

$Q$ = a finite set of states

$\Sigma$ = a finite, nonempty input alphabet

$\delta$ = a series of transition functions

$q_0$ = the starting state

$F$ = the set of accepting states

There must be exactly one transition function for every input symbol in $\Sigma$ from each state.

DFAs can be represented by diagrams of this form:

Write a description of the DFA shown above. Describe in words what it does.

Show Answer

$Q = \{s_1, s_2\}$

$\Sigma\ = \{0,1\}$

The following table describes $\delta$:

current state	input symbol	new state
$s_1$	1	$s_1$
$s_1$	0	$s_2$
$s_2$	1	$s_2$
$s_2$	0	$s_1$

$q_0 = s_1$

$F= {s_1}$

This DFA recognizes all strings that have an even number of 0’s (and any number of 1’s). This means that if you run any input string that has an even number of 0’s, the string will finish in the accepting state. If you run a string with an odd number of 0’s, the string will finish in $s_2$, which is not an accepting state.

Here is a DFA diagram that describes a few simple moves that a character in a video game can do: stand, run, and jump. The buttons that a player can use to control this particular character are "Up," "A," or the player can press no button.

Using the state diagram for the video game character above, describe how a player can control their character to go from standing to running to jumping.

Show Answer

In the standing state, the player can press nothing and remain in the standing state, then, to transition to the running state, the user must press the "Up" button. In the running state, the user can continue to make their character run by pressing the "Up" button, and then to transition to the jump state, the user must press "A."

Draw a diagram for a DFA that recognizes the following language: The language of all strings that end with a 1.

Show Answer

Nondeterministic Finite Automata

Similar to a DFA, a nondeterministic finite automaton (NDFA or NFA) is described by a five-element tuple: $(Q, \Sigma, \delta, q_0, F)$.

$Q$ = a finite set of states

$\Sigma$ = a finite, nonempty input alphabet

$\delta$ = a series of transition functions

$q_0$ = the starting state

$F$ = the set of accepting states

Unlike DFAs, NDFAs are not required to have transition functions for every symbol in $\Sigma$, and there can be multiple transition functions in the same state for the same symbol. Additionally, NDFAs can use null transitions, which are indicated by $\epsilon$. Null transitions allow the machine to jump from one state to another without having to read a symbol.

An NDFA accepts a string $x$ if there exists a path that is compatible with that string that ends in an accept state.

NDFAs can be represented by diagrams of this form:

source^[1]

Describe the language that the NDFA above recognizes.

Show Answer

The NDFA above recognizes strings that end in “10” and strings that end in “01.”

State $a$ is the start state, and from there, we can create a string with however many 1’s and 0’s in any order, and then transfer to state $b$ or state $e$, or we can immediately transfer to state $b$ or state $e$. In any case, the NDFA will only accept a string that reaches state $d$ or state $g$. In order to reach state $d$ or state $g$, the string must end with a “01” (for state $d$) or a “10” (for state $g$).

For example, the following strings are all recognized by this NDFA.

• 00000000010
• 10
• 01
• 1111101

Draw a diagram for the NDFA that describes the following language: The language of all strings that end with a 1.

Show Answer

One might think that NDFAs can solve problems that DFAs cannot, but DFAs are just as powerful as NDFAs. However, a DFA will require many more states and transitions than an NDFA would take to solve the same problem. To see this, examine the example in the proof below.

Proof Sketch

NDFAs are equivalent to DFAs

To convert a DFA into an NDFA, just define an NDFA that has all the same states, accept states, transitions, and alphabet symbols as the DFA. Essentially, the NDFA “ignores” its nondeterminism because it does not use null transitions and has exactly one transition per symbol in each state.

DFAs are equivalent to NDFAs

If an NDFA uses $n$ states, a DFA would require up to $2^n$ states in order to solve the same problem. To translate an NDFA into a DFA, use powerset construction. For example, if an NDFA has 3 states, the corresponding DFA would have the following state set: $\{\emptyset, \{a\},\{b\},\{c\},\{a,b\},\{a,c\},\{b,c\},\{a,b,c\}\}$. Each element in the state set represents a state in the DFA. We can determine the transition functions between these states for each element of the set.

source^[1]

For example, in the DFA, state $\{a\}$ goes to $\{a,b\}$ on input 0 since in the NDFA above, state $\{a\}$ goes into both state $a$ and state $b$. This process is repeated for the remaining states in the set of the DFA.

Since DFAs are equivalent to NDFAs, it follows that a language is regular if and only if it is recognized by an NDFA.

With a few additional proofs, one can show that NDFAs and DFAs are equivalent to regular expressions.

By definition, a language is regular if and only if there is a DFA that recognizes it. Since DFAs are equivalent to NDFAs, it follows that a language is regular if and only if there is an NDFA that recognizes it. Therefore, DFAs and NDFAs recognize all regular languages.

One limitation of finite state machines is that they can only recognize regular languages. Regular languages make up only a small, finite portion of possible languages. See context free grammars and Turing machines.

1. Aaronson, S. 6.045J Automata, Computability, and Complexity: Lecture 3, Spring 2011. Retrieved April,1, 2016, from http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-045j-automata-computability-and-complexity-spring-2011