Finite Automata

An automaton with a set of states, and its “control” moves from state to state in response to external “inputs” is called a finite automaton.

A finite automaton, FA, provides the simplest model of a computing device. It has a central processor of finite capacity and it is based on the concept of state. It can also be given a formal mathematical definition. Finite automata are used for pattern matching in text editors, for compiler lexical analysis.

Another useful notion is the notion of nondeterministic automaton.

We can prove that deterministic finite automata, DFA, recognize the same class of languages as NDFA, ie. they are equivalent formalisms.

It is also possible to prove that given a language L there exists a unique (up to isomorphism) minimum finite state automaton that accepts it, i.e. an automaton with a minimum set of states.

The automata in the examples are deterministic, that is, once their state and input are given, their evolution is uniquely determined.

Deterministic Finite Automata

an informal description

A deterministic finite state automaton (DFA) is a simple language recognition device. It can be seen as a machine working to give an indication about strings which are given in input or it can be given a mathematical definition.

Strings are fed into the device by means of an input tape, which is divided into squares, each one holding one symbol. The main part of the machine itself is a black box which is, at any specified moment, in one of a finite number of distinct internal states, among which we distinguish an initial state and some final states. This black box, called the finite control, can sense what symbol is written at any position of the input tape by means of a movable reading head. Initially, the reading head is placed at the leftmost square of the tape and the finite control is set in a designated initial state.

At regular intervals the automaton reads one symbol from the input tape and then enters a new state that depends only on the current state and the symbol just read. After reading an input symbol, the reading head moves one square to the right on the input tape so that on the next move it will read the symbol in the next tape square.

In our picture (fig.1)Q0 is the initial state, a is the first symbol to be read and the machine is set so that when an a is read in state Q0 it reaches state Q1.

This process is repeated again and again (fig.2). Eventually the reading head reaches the end on the input string. The automaton then indicates its approval or disapproval of what it has read by the state it is in at the end: if it winds up in one of the set of final states the input string is considered to be accepted. The language accepted by the machine is the set of the strings it accepts.

figure .1

figure.2

D.F.A mathematical definition

A deterministic finite state automaton is a quintuple <Q,I,d,q0,F>; where:

Q is a finite set of states;
I is a finite set of input symbols;
d is the transition function that takes as arguments a state and an input symbol and returns a state . The transition function will commonly be denoted d . In our informal graph representation of automata, d was represented by arcs between states and the labels on the arcs. If ‘q’ is a state , and ‘a’ is a input symbol, then d(q,a) is that state ‘p’ such that there is an arc labelled ‘a’ from ‘q’ to square of ‘p’.
q0 element of Q is the initial state;
F contained in Q is the set of final states (or accepting states).

The function delta can be extended to the domain Q X I*, defining the function delta* as follows:

d*(q,lambda)=q for each q belonging to Q
d*(q,xa)=d(delta*(q,x),a) for each x belonging to I* and for each a belonging to I.

The language L(A) accepted or recognized by the automaton A is defined as the set of words accepted by A:

L(A) = { x| d* (q0, x) belongs to F}

Extended transition function

Suppose ‘w’ is a string of the form ‘xa’; ie a is the last symbol of ‘w’,and x is the string consisting of all but the last symbol.Then

d^(q,w)=d (dhat(q,x),a);

To compute d^t(q,w) first compute d^(q,x) ie the state of the automaton after processing all but last symbol of ‘w’. Suppose this state is ‘p’ ie d^(q,x)=p. Then d^(q,w)=d(p,a).