AUTOMATA THEORY AND IT’S TYPES

NAME: UMAIR ALI

ROLL NO: 20104009-003
COURSE TITLE: MODELING AND
SIMULATION
COURSE CODE: MATH 4005
DEPARTMENT: BS-MATHAMATICS
SEMESTER: 8th
SUBMITTED TO: SIR SHAKEEL

ASSIGNMENT NO 01

1
 AUTOMATA THEORY AND IT’S TYPES

AUTOMATA THEORY
Automaton, in plural Automatons or Automata, is a self-operating device. Automata
Theory lies in Computer Science and Discrete Mathematics. It is the study of the abstract
machine in theoretical computer science. It is designed to automatically follow a
predetermined sequence of operations. The term automata is derived from the Greek
word αὐτόματα, which means 'self-making'. It means it automatically processes the
production of specific work.

AUTOMATA INVENTOR
The Jacques de Vaucanson was responsible for the invention of innovative and impressive
Automata.
As all of us know, every machine takes some input. That input can have to pass through
multiple stages. Every stage has some information on what to do with the incoming input. It
can either reject the input or return some output. So, that needs computation of the machine.
This is the basic concepts behind Automata Theory.

Characteristics of Automata
The basic characteristics of automata include the following:
❑ INPUTS - It is a finite set of input symbols or sequences of symbols, {x1, x2,
x3,...,xk}, where k is the number of inputs.
❑ OUTPUTS - It is a finite set of output symbols, {y1, y2, y3,...,ym}, where m is the
number of outputs.
❑ STATES - It is a finite set, denoted by Q whose definition depends on the type of
automaton.

AUTOMATA TERMINOLOGIES
These are some basic terminology used in Automata Theory.

➢ Alphabets
A finite, non-empty set of symbols is known as Alphabet. It is denoted by Greek letter ∑.
This is the set over which the strings are defined. These are some examples of alphabets.

❖ Examples of Alphabets
∑ = {a,b,c,d}
∑ = {A,B,C} // It is an alphabet
∑ = {0,1,2,3} // It is an alphabet of digits
∑ = {0,1,a,b,c,d} // It is an alphabet of digits

2
 AUTOMATA THEORY AND IT’S TYPES

➢ Strings
A String over an alphabet is a finite sequence of any symbol selected from the set of alphabet
symbols. It is generally denoted by w.
An empty string is denoted by as є or λ.

❖ Examples of Strings
∑1 = {0,1}
w = 100111 // It is a string over an alphabet ∑1
∑2 = {a,b,c}
w2 = abaccab // It is a string over an alphabet ∑2

➢ Length of string
The number of symbols present in the string is known as the Length of the string. The
length of the string is denoted by |w|. For the string S = 'adadda', the length of the string is |S|
= 6.

➢ Languages
A set of valid strings over a finite alphabet. It is denoted by L. Language can be
finite or infinite.
Empty Language - The empty string contains no string, denoted by {} or ∅.

❖ Example of Language
∑ = {a,b}

L = {aa, ab, ba, bb}

Here, the language takes all the possible strings of length 2 over the set Σ = {a, b}.

➢ Kleene Closure
The set ∑+ is the infinite set of all possible strings of all possible length over Σ.
It is generated by concatenating arbitrary elements of a set of strings. It is also
called Positive Closure or Kleene Star.

❖ Examples of Kleene Closure

∑ = {a,b}
∑ * = {a, b aa, ab, ba, bb,..}
∑ 1 = {ab,c}
∑ 1 * = {ab, c, abc, abab, cc, abababc,..}

3
 AUTOMATA THEORY AND IT’S TYPES

TYPES OF AUTOMATA

We will only discuss about the Finite Automata & it’s types.

FINITE AUTOMATA
Finite Automata (FA) is the simplest machine to recognize
patterns. It is used to characterize a Regular Language.
For example: /baa+!/.
Also it is used to analyze and recognize Natural language
Expressions.
The finite automata or finite state machine is an abstract
machine that has five elements or tuples. It has a set of
states and rules for moving from one state to another but it
depends upon the applied input symbol. Based on the states
and the set of rules the input string can be either accepted
or rejected. Basically, it is an abstract model of a digital
computer which reads an input string and changes its
internal state depending on the current input symbol. Every
automaton defines a language i.e. set of strings it accepts. The figure shows some essential
features of general automation.

4
 AUTOMATA THEORY AND IT’S TYPES

Formal Definition of Finite Automata

A Finite Automata has several parts. It has a set of states and rules for going from one state
to another, depending on the input symbol. The list of five objects is sets of states, start
state, input alphabet, rules for moving and accept state. In a mathematical language, a list
of five objects is obtained called five tuples.

Q, ∑, δ, q0, F

Q - Finite set of states,

∑ - alphabet of input symbols,
δ: Q × ∑ → Q - transition function,
q0 (q0 ∈ Q) - initial state,
F - A set of final state (F ⊆ Q).

State Diagram of Finite Automata

Suppose, here is a state diagram of finite automaton M.

The finite automata M is written as-

M = (Q, ∑, δ, q0, F)
where,
Q = {q0, q1, q2},
∑ = {0,1},
δ is described as -
0 1

q0 q1 q0

q1 q1 q2

q2 q1 q1

q0, is the start state, & F = {q1}, is the final state.

5
 AUTOMATA THEORY AND IT’S TYPES

Classification Of Finite Automata

Finite Automata is classified into two types
❑ Deterministic Finite Automata (DFA)
❑ Nondeterministic Finite Automata (NFA)

DETERMINISTIC FINITE AUTOMATA (DFA)

The term Deterministic means the uniqueness of the computation. It is a finite
state machine that either accepts or rejects strings of symbols, and for each input
string it returns a unique computation. It has a set of states and rules for going
from one state to another, depending on the input symbol. When the machine is
in a given state and reads the next input symbol . It reads only one input symbol
at a time from the tape, and after that it decides whether to accept or reject the
input.
A DFA is defined as an abstract mathematical concept, but is often implemented
in hardware and software for solving different specific problems such as lexical
analysis and pattern matching.

➢ Parts of DFA
A Deterministic Finite Automata has three parts-
❖ A tape to hold the input string.
❖ A tape head to read the input symbols.
❖ A control that contains three main parts – set of start states, set of transition
functions and final states.

➢ Formal Definition of DFA

A DFA is five tuples, consisting of

Q, ∑, δ, q0, F

Q- A finite set of states.

∑- Alphabet of input symbols.
δ- A transition function that takes as argument a state and a symbol and returns a state.
Q×Σ→Q
q0- A start state.
F- A set of final or accept states.

6
 AUTOMATA THEORY AND IT’S TYPES

➢ Represent DFA with Transition Table

Here is an example of DFA using a transition table and a graph. The → indicates
the start state and the * indicates the final state.

0 1

→ q0 q1 q0

q1 q1 q2

*q2 q2 q2

➢ DFA transition diagram of above transition table.

The formal DFA of the above example is -

Q = {q0, q1, q2}
Σ = {0,1}
q0(start state) = q0
δ: Q×Σ→Q
F (final state) = {q2}

➢ Language accepted by DFA

The language L(M), accepted and recognized by a DFA is the set of all strings w accepted
by M -
L(M) = {w ∈ Σ* | M accepts w}

7
 AUTOMATA THEORY AND IT’S TYPES

NONDETERMINISTIC FINITE AUTOMATA (NFA)

Non Deterministic Finite Automata has great importance in the theory of computation.
In Deterministic Finite Automata, the next input symbol is determined in the next step. But,
In Non Deterministic Finite Automata, there are several choices may exist at any point in
the next state. So, every Deterministic Finite Automata is automatically a Non Deterministic
Finite Automata. NFAs are used in the implementation of regular expressions.
In NFA, each state can have zero, one, two, or more transitions corresponding to a particular
input symbol. It can also have an empty (ε) transition, where NFA can change state without
consuming an input symbol.

➢ Features of NFA
❖ NFA can perform parallel computation, multiple processes can be running
concurrently.
❖ It can permit null or empty (ε) string transition.
❖ In NFA, a state may have zero, one or many exciting arrows for each alphabet
symbol. It has a choice of where to move to the next state.
❖ We can easily convert every NFA into an equivalent DFA.
❖ It is easy to understand and functionality may be easier than a DFA.

➢ Formal definition of NFA

Non Deterministic Finite Automata also has 5 tuples.

(Q, ∑, δ, q0, F)

Q - It has a finite set of states.

∑ - Alphabet of input symbols.
δ - A transition function that takes as argument a state and a symbol and returns a state.
δ: Q × (Σ ∪ {∈}) -> p(Q)
where, P(Q) is the power set of Q.
q0 - A start state.
F - A set of final or accepting states.
A string is accepted by a NFA if δ (q0, w) contains at least one final state.

8
 AUTOMATA THEORY AND IT’S TYPES

➢ Represent NFA with Transition Table

Here is an example of an NFA using a transition table and a graph.

0 1 ε

q0 {q0} {q0,q1} ∅

q1 {q2} {q2} {q2}

q2 {q3} {q3} ∅

q3 ∅ ∅ ∅

➢NFA transition diagram of above transition table.

➢ Implementation Of NFA
There are many ways to implement a NFA:

❖ Convert to the equivalent DFA. In some case’s this may cause exponential blowup in
the number of states.
❖ Keep a set data structure of all states which the NFA might currently be in. On the
consumption of an input symbol, unite the results of the transition function applied to
all current states to get the set of next states; if ε-moves are allowed, include all states
reachable by such a move (ε-closure). Each step requires at most s2 computations,
where s is the number of states of the NFA. On the consumption of the last input
symbol, if one of the current states is a final state, the machine accepts the string. A
string of length n can be processed in time O(ns2) and space O(s).
❖ Create multiple copies. For each n way decision, the NFA creates up to n−1 copies of
the machine. Each will enter a separate state. If, upon consuming the last input

9
 AUTOMATA THEORY AND IT’S TYPES

symbol, at least one copy of the NFA is in the accepting state, the NFA will accept.
(This, too, requires linear storage with respect to the number of NFA states, as there
can be one machine for every NFA state.)
❖ Explicitly propagate tokens through the transition structure of the NFA and match
whenever a token reaches the final state. This is sometimes useful when the NFA
should encode additional context about the events that triggered the transition. (For an
implementation that uses this technique to keep track of object references have a look
at Trace matches)

ADVANTAGES AND DISADVANTAGES OF DFA & NFA

❖ DFAs are equivalent in computing power to nondeterministic finite automata (NFAs).
This is because, firstly any DFA is also an NFA, so an NFA can do what a DFA can
do. Also, given an NFA, using the powerset construction one can build a DFA that
recognizes the same language as the NFA, although the DFA could have
exponentially larger number of states than the NFA. However, even though NFAs are
computationally equivalent to DFAs, the above-mentioned problems are not
necessarily solved efficiently also for NFAs. The non-universality problem for NFAs
is PSPACE complete since there are small NFAs with shortest rejecting word in
exponential size. A DFA is universal if and only if all states are final states, but this
does not hold for NFAs. The Equality, Inclusion and Minimization Problems are also
PSPACE complete since they require forming the complement of an NFA which
results in an exponential blow up of size.
❖ On the other hand, finite-state automata are of strictly limited power in the languages
they can recognize; many simple languages, including any problem that requires more
than constant space to solve, cannot be recognized by a DFA. The classic example of
a simply described language that no DFA can recognize is bracket or Dyck language,
i.e., the language that consists of properly paired brackets such as word "(()())".
Intuitively, no DFA can recognize the Dyck language because DFAs are not capable of
counting: a DFA-like automaton needs to have a state to represent any possible
number of "currently open" parentheses, meaning it would need an unbounded
number of states. Another simpler example is the language consisting of strings of the
form anbn for some finite but arbitrary number of a's, followed by an equal number
of b's.

10