Theory of Automata

Definition of Automaton:

An Automaton is a “self-acting” system that operates on a set of input symbols (one at a time) and decides whether or not to accept the given input sequence. Sometimes it may optionally produce some output sequence as well.

Formally an Automaton may be defined to consist of the following:

1.       Input: A Set of Input Symbols or the Alphabet. Often denoted by the symbol ∑ (Sigma).

2.       Output: A set of output symbols. Denoted by O.

3.       States: At any instant the automaton can be in one of the states or ‘Transition States’. Denoted by q1, q2… qn.

4.       State relation: it defines the movement of the system from a given state and input symbol to some next state.

5.       Output Relation: it is either related to the current state only or to both the input and the current state.


Analytic description of a Finite Automaton:

A finite automaton is represented by the 5-tuple (Q, ∑, δ, q0, F) where:

(i)                  Q is a finite nonempty set of states.

(ii)                ∑ is a finite nonempty set of inputs called the input alphabet.

(iii)               δ is the transition function which maps Q X ∑ into Q. This is the function which describes the change of states (transition) when input symbols are supplied to the automaton. This mapping is usually represented by a transition table or a transition diagram. (This form is the Direct Transition Function)

(iv)              q0 ϵ Q is the start state or the initial state before any input symbol has been supplied to the automaton.

(v)                F ⊆ Q is the set of final states. (There can be more than one of these)

Theory of Automata
5 (100%) 1 vote

Leave a Reply