# Finite state machine

A finite state machine is a way of defining a language (see Strings and languages). We give a string to the machine, which examines the string one character by one, and at the end decides whether the string is the language or not.

A non-deterministic finite state machine (also called 'finite automaton') is a five-tuple where

• is a finite alphabet
• is a finite set of states
• is a transition relation
• is the initial state of the automaton
• is the set of final states

We graphically represent finite state machines using a graph.

• the nodes of the graph are the states , represented using circles
• the graph has an edge from to labelled by if and only
• we draw a double circle around each state if and only if
• we put a symbol in front of the initial state

Example finite state machine:

We formalize the operation of a finite state machine as follows.

If and , an execution of a finite state machine on is a sequence

where , such that for all .

If , we define as the set of all states in which the automaton could be while processing the word . Formally, we define as the set of all states such that there exists an execution with given , with , and witn some .

An accepting execution is an execution where and . We say that accepts the string iff there exists an accepting execution of on . We define the language of the automaton, denoted , as the set of all strings that accepts.

We then have

Example: the example automaton above accepts the language , which we can denote by .

What is the automaton accepting strings of the form where are arbitrary strings?

A state machine is called deterministic iff for every pair there exists exactly one such that .

References