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 .