Automata – What is it?

Automata theory (also known as Theory Of Computation) is a theoretical branch of Computer Science and Mathematics, which mainly deals with the logic of computation with respect to simple machines, referred to as automata.

Automata* enables scientists to understand how machines compute the functions and solve problems. The main motivation behind developing Automata Theory was to develop methods to describe and analyze the dynamic behavior of discrete systems.

Automata originated from the word “Automaton” which is closely related to “Automation”.

An automaton with a finite number of states is called a Finite Automaton (FA) or Finite State Machine (FSM).

Related Terminologies

Symbols:

Symbols are an entity or individual objects(smallest possible), which can be any letter, alphabet or any picture.

Example:

1, a, b, #

Alphabet

Definition − An alphabet is any finite set of symbols.It is denoted by ∑.
Example − ∑ = {a, b, c, d} is an alphabet set where ‘a’, ‘b’, ‘c’, and ‘d’ are symbols.
Examples:
1. ∑ = {a, b}
2. ∑ = {A, B, C, D}
3. ∑ = {0, 1, 2}
4. ∑ = {0, 1, ....., 5]
5. ∑ = {#, β, Δ}

String

Definition − A string is a finite sequence of symbols taken from ∑.
Example − ‘cabcad’ is a valid string on the alphabet set ∑ = {a, b, c, d}

Length of a String

Definition − It is the number of symbols present in a string. (Denoted by |S|).
Examples −
- If S = ‘cabcad’, |S|= 6
- If |S|= 0, it is called an empty string (Denoted by λ or ε)

Kleene Star

Definition − The Kleene star, ∑*, is a unary operator on a set of symbols or strings, ∑, that gives the infinite set of all possible strings of all possible lengths over ∑ including λ.
Representation − ∑* = ∑₀ ∪ ∑₁ ∪ ∑₂ ∪……. where ∑_p is the set of all possible strings of length p.
Example − If ∑ = {a, b}, ∑* = {λ, a, b, aa, ab, ba, bb,………..}

Kleene Closure / Plus

Definition − The set ∑⁺ is the infinite set of all possible strings of all possible lengths over ∑ excluding λ.
Representation − ∑⁺ = ∑₁ ∪ ∑₂ ∪ ∑₃ ∪…….

∑⁺ = ∑* − { λ }
Example − If ∑ = { a, b } , ∑⁺ = { a, b, aa, ab, ba, bb,………..}

Language
Definition − A language is a subset of ∑* for some alphabet ∑. It can be finite or infinite.
Example − If the language takes all possible strings of length 2 over ∑ = {a, b}, then L = { ab, aa, ba, bb }

Example: Finite Language

L1 = {Set of string of length 2}

     = {aa, bb, ba, bb}

Example: Infinite Language

L2 = {Set of all strings starts with 'a'}

     = {a, aa, aaa, abb, abbb, ababb,.....}

Formal definition of a Finite Automaton

An automaton can be represented by a 5-tuple (Q, ∑, δ, q₀, F), where −

Q is a finite set of states.
∑ is a finite set of symbols, called the alphabet of the automaton.
δ is the transition function.
q₀ is the initial state from where any input is processed (q₀ ∈ Q).
F is a set of final state/states of Q (F ⊆ Q).

Formal Notation used in the representation of Finite Automata

We can represent Finite automata in two ways, which are given below:

Transition diagram

The transition diagram is also called a transition graph; it is represented by a diagraph. A transition graph consists of three things:

Arrow (->): The initial state in the transition diagram is marked with an arrow.
Circle : Each circle represents the state.
Double circle : Double circle indicates the final state or accepting state.

Transition Table

It is the tabular representation of the behavior of the transition function that takes two arguments, the first is a state, and the other is input, and it returns a value, which is the new state of the automata. It represents all the moves of finite-state function based on the current state and input. In the transition table, the initial state is represented with an arrow, and the final state is represented by a single circle. Formally a transition table is a 2-dimensional array, which consists of rows and columns where:

The rows in the transition table represent the states.
The columns contain the state in which the machine will move on the input alphabet.

Types of Finite Automata

Examples:

The example of Finite state Automata is Automatic door controller because it has limited memory for detecting the present state of the controller, automatic doors are often found at entrance and exists of various hotels, supermarkets, theaters and hospitals etc. Automatic door have two pads that are used for detection:

Front Pad: This is located at front of the doorway to detect the presence of the person.

Rear Pad: This pad is located at backside of the doorway. In this, controller hold the door to open till the person passes all the way through it.

Some other examples of finite automata are elevator, digital watches, dish washes and calculators.

Important features of Finite Automata

Input: Finite Automata takes some input and with the use of this input we can produce some output. The input of the automata is given in the input tape used in the automata. This tape is divided into cells or squares which can hold one symbol at a time.

Output: Finite Automata produce some output with the use of some input.

States of Automata: Automata have finite number of input states. States of Automata like q₀, q₁…q_n.

State Relation: State relations show how automata moves from one state to another state. The next state of the automata at any instant of time is determined by the present state and the input.

Advantages of finite Automata

Below are some advantages of Finite State Automata and Finite State Machine:

Finite state machines are very flexible.
Well suited for domains where execution time is shared between various modules.
In finite state automata, we can easily determine the reachability of an input state whether it is accepted or rejected.

Disadvantages of finite Automata

Below are some disadvantages of Finite State Automata and Finite State Machine:

Finite state Automata have very limited amount of memory.
Various multiplications operations on large numbers cannot be carried out on finite automata, because it has limited memory and it cannot remember the full-length sequence of large numbers.
Not applicable for all types of applications.
Finite state Automata cannot process Natural Language processes.
Finite state automata have less computational power than some other models of computation used in automata such as Push down Automata, linear bounded automata and Turing machine.

Applications of Finite Automata

Finite Automata is used in various fields like science, mathematics, and engineering. Below are some applications of finite automata:

Finite state Automata used in Word Processor Programs to provide features, which allow us to search for a given string.

It is used in Digital Logic Design to control units for a disk or an Input/output controller on a process.
It is used in Lexical Analysis phase in complier design.
It is used in various spell checker applications.
It is used in various Circuit switching design.
It is used in various text editors.

Deterministic Finite Automaton

Finite Automaton can be classified into two types −

Deterministic Finite Automaton (DFA)
Non-deterministic Finite Automaton (NDFA / NFA)

Deterministic Finite Automaton (DFA)

In DFA, for each input symbol, one can determine the state to which the machine will move. Hence, it is called Deterministic Automaton. As it has a finite number of states, the machine is called Deterministic Finite Machine or Deterministic Finite Automaton.

Formal Definition of a DFA

A DFA can be represented by a 5-tuple (Q, ∑, δ, q₀, F) where −

Q is a finite set of states.
∑ is a finite set of symbols called the alphabet.
δ is the transition function where δ: Q × ∑ → Q
q₀ is the initial state from where any input is processed (q₀ ∈ Q).
F is a set of final state/states of Q (F ⊆ Q).

Graphical Representation of a DFA

A DFA is represented by digraphs called state diagram.

The vertices represent the states.
The arcs labeled with an input alphabet show the transitions.
The initial state is denoted by an empty single incoming arc.
The final state is indicated by double circles.

Example

Let a deterministic finite automaton be →

Q = {a, b, c},
∑ = {0, 1},
q₀ = {a},
F = {c},

and

Transition function δ as shown by the following table −

Present State	Next State for Input 0	Next State for Input 1
a	a	b
b	c	a
c	b	c

Its graphical representation would be as follows −

Non-deterministic Finite Automaton

In NDFA, for a particular input symbol, the machine can move to any combination of the states in the machine. In other words, the exact state to which the machine moves cannot be determined. Hence, it is called Non-deterministic Automaton. As it has finite number of states, the machine is called Non-deterministic Finite Machine or Non-deterministic Finite Automaton.

Formal Definition of an NDFA

An NDFA can be represented by a 5-tuple (Q, ∑, δ, q₀, F) where −

Q is a finite set of states.
∑ is a finite set of symbols called the alphabets.
δ is the transition function where δ: Q × ∑ → 2^Q

(Here the power set of Q (2^Q) has been taken because in case of NDFA, from a state, transition can occur to any combination of Q states)
q₀ is the initial state from where any input is processed (q₀ ∈ Q).
F is a set of final state/states of Q (F ⊆ Q).

Graphical Representation of an NDFA: (same as DFA)

An NDFA is represented by digraphs called state diagram.

The vertices represent the states.
The arcs labeled with an input alphabet show the transitions.
The initial state is denoted by an empty single incoming arc.
The final state is indicated by double circles.

Example

Let a non-deterministic finite automaton be →

Q = {a, b, c}
∑ = {0, 1}
q₀ = {a}
F = {c}

The transition function δ as shown below −

Present State	Next State for Input 0	Next State for Input 1
a	a, b	b
b	c	a, c
c	b, c	c

Its graphical representation would be as follows −

DFA vs NDFA

The following table lists the differences between DFA and NDFA.

DFA	NDFA
The transition from a state is to a single particular next state for each input symbol. Hence it is called deterministic.	The transition from a state can be to multiple next states for each input symbol. Hence it is called non-deterministic.
Empty string transitions are not seen in DFA.	NDFA permits empty string transitions.
Backtracking is allowed in DFA	In NDFA, backtracking is not always possible.
Requires more space.	Requires less space.
A string is accepted by a DFA, if it transits to a final state.	A string is accepted by a NDFA, if at least one of all possible transitions ends in a final state.

Search This Blog

BCA - BSc Notes (Solapur University)

Theory Of Computation