Finite State Machines


What is a Finite State Machine?

The simplest type of computing machine that is worth considering is called a ‘finite state machine’. Finite state machines may sound like a very dry and boring topic but they reveal a lot about the power of different types of computing machine. Every Turing machine includes a finite state machine so there is a sense in which they come first. They also turn out to be very useful in practice.

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. A regular language is a language that can be expressed with a regular expression or a deterministic or non-deterministic finite automata or state machine. A language is a set of strings which are made up of characters from a specified alphabet, or set of symbols. Regular languages are a subset of the set of all strings. Regular languages are used in parsing and designing programming languages and are one of the first concepts taught in computability courses. 

Types of Finite State Machines

There are two types of finite state machines (FSMs): deterministic finite state machines, often called deterministic finite automata (DFA), and nondeterministic finite state machines, often called nondeterministic finite automata (NDFA).

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.

Formal Definition of FSMs

DFAs and NDFAs are described by a five-element tuple : .

 = a finite set of states

= a finite, nonempty inputalphabet

 = a series of transition functions

 = the starting state

 = the set of accepting states

However, for DFAs there must be exactly one transition function for every input symbol in from each state. On the other hand, NDFAs are not required to have transition functions for every symbol in , 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 ε. Null transitions allow the machine to jump from one state to another without having to read a symbol.

And this is it by now, over the next post i will talk about graphic representations of FSMs and languages accepted by some of them as examples.


Leave a Reply

Your email address will not be published. Required fields are marked *