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