UNIT- I AUTOMATA

Introduction to formal proof – Additional forms of proof – Inductive proofs –Finite Automata (FA) –
Deterministic Finite Automata (DFA)– Non-deterministic Finite Automata (NFA) – Finite Automata with
Epsilon transitions.

Unit No: I Name: Automata

In theoretical computer science, the theory of computation is the branch that deals with
whether and how efficiently problems can be solved on a model of computation, using an
algorithm. The field is divided into three major branches: automata theory, computability theory
and computational complexity theory.
In order to perform a rigorous study of computation, computer scientists work with a
mathematical abstraction of computers called a model of computation. There are several
models in use, but the most commonly examined is the Turing machine.
Automata theory
In theoretical computer science, automata theory is the study of abstract machines (or
more appropriately, abstract 'mathematical' machines or systems) and the computational
problems that can be solved using these machines. These abstract machines are called automata.
This automaton consists of
• states (represented in the figure by circles),
• and transitions (represented by arrows).
As the automaton sees a symbol of input, it makes a transition (or jump) to another state,
according to its transition function (which takes the current state and the recent symbol as its
inputs).
Uses of Automata: compiler design and parsing.

Introduction to formal
proof: Basic Symbols used :
U – Union ∩- Conjunction ϵ - Empty String Φ – NULL set
7- negation ‘ – compliment = > implies

Additive inverse: a+(-a)=0

Multiplicative inverse: a*1/a=1
Universal set U={1,2,3,4,5}
Subset A={1,3}
A’ ={2,4,5}
Absorption law: AU(A ∩B) = A, A∩(AUB) = A
De Morgan’s Law:
(AUB)’ =A’ ∩ B’
(A∩B)’ = A’ U B’
Double compliment
(A’)’ =A
A ∩ A’ = Φ

Logic relations:
a b = > 7a U b
7(a∩b)=7a U 7b

Relations:
Let a and b be two sets a relation R contains aXb.
Relations used in TOC:
Reflexive: a = a
Symmetric: aRb = > bRa
Transition: aRb, bRc = > aRc
If a given relation is reflexive, symmentric and transitive then the relation is called equivalence
relation.

Deductive proof: Consists of sequence of statements whose truth lead us from some
initial statement called the hypothesis or the give statement to a conclusion statement.

Additional forms of proof:

Proof of sets
Proof by contradiction
Proof by counter example

Direct proof (AKA) Constructive proof:

If p is true then q is true. Eg: if a and b are odd numbers then product is also an odd
number. Odd number can be represented as 2n+1 a=2x+1, b=2y+1
product of a X b = (2x+1) X (2y+1)
= 2(2xy+x+y)+1 = 2z+1 (odd number)
Proof by contrapositive:
Proof by Contradiction:

H and not C implies falsehood.

Be regarded as an observation than a theorem.

For any sets a,b,c if a∩b = Φ and c is a subset of b the prove that a∩c
=Φ Given : a∩b=Φ and c subset b
Assume: a∩c Φ
Then
= > a∩b Φ = > a∩c=Φ(i.e., the assumption is wrong)
Proof by mathematical Induction:

Languages :

The languages we consider for our discussion is an abstraction of natural languages.

That is, our focus here is on formal languages that need precise and formal definitions.
Programming languages belong to this category.

Symbols :

Symbols are indivisible objects or entity that cannot be defined. That is, symbols are the
atoms of the world of languages. A symbol is any single object such as , a, 0, 1, #,
begin, or do.

Alphabets :

An alphabet is a finite, nonempty set of symbols. The alphabet of a language is normally

denoted by . When more than one alphabets are considered for discussion, then
subscripts may be used or sometimes other symbol like G may also be introduced.

Example :

Strings or Words over Alphabet :

A string or word over an alphabet is a finite sequence of concatenated symbols of.

Example : 0110, 11, 001 are three strings over the binary alphabet { 0, 1 } .
aab, abcb, b, cc are four strings over the alphabet { a, b, c }.

It is not the case that a string over some alphabet should contain all the symbols from
the alphabet. For example, the string cc over the alphabet { a, b, c } does not contain
the symbols a and b. Hence, it is true that a string over an alphabet is also a string over
any superset of that alphabet.

Length of a string :
The number of symbols in a string w is called its length, denoted by |w|.

Example : | 011 | = 4, |11| = 2, | b | = 1

Convention : We will use small case letters towards the beginning of the English
alphabet to denote symbols of an alphabet and small case letters towards the end to
denote strings over an alphabet. That is, (symbols) and
are strings.

Some String Operations :

Let and be two strings. The concatenation of x and y
denoted by xy, is the string . That is, the concatenation of x and
y denoted by xy is the string that has a copy of x followed by a copy of y without any
intervening space between them.

Example : Consider the string 011 over the binary alphabet. All the prefixes, suffixes
and substrings of this string are listed below.

Prefixes: ε, 0, 01, 011.

Suffixes: ε, 1, 11, 011.
Substrings: ε, 0, 1, 01, 11, 011.

Note that x is a prefix (suffix or substring) to x, for any string x and ε is a prefix (suffix
or substring) to any string.

A string x is a proper prefix (suffix) of string y if x is a prefix (suffix) of y and x ≠ y.

In the above example, all prefixes except 011 are proper prefixes.

Powers of Strings : For any string x and integer , we use to denote the string
formed by sequentially concatenating n copies of x. We can also give an inductive
definition of as follows: = e, if
n = 0 ; otherwise

Example : If x = 011, then = 011011011, = 011 and

Powers of Alphabets :
We write (for some integer k) to denote the set of strings of length k with
symbols from . In other words,
= { w | w is a string over and | w | = k}. Hence, for any alphabet, denotes the set
of all strings of length zero. That is, = { e }. For the binary alphabet { 0, 1 } we
have the following.

The set of all strings over an alphabet is denoted by . That is,

The set contains all the strings that can be generated by iteratively concatenating
symbols from any number of times.

Example : If = { a, b }, then = { ε, a, b, aa, ab, ba, bb, aaa, aab, aba, abb, baa, …}.

Please note that if , then that is . It may look odd that one can
proceed from the empty set to a non-empty set by iterated concatenation. But there is a
reason for this and we accept this convention

The set of all nonempty strings over an alphabet is denoted by . That is,

Note that is infinite. It contains no infinite strings but strings of arbitrary lengths.

Reversal :
For any string the reversal of the string is .

An inductive definition of reversal can be given as follows:

7
 CS2303 THEORY OF COMPUTATION

Languages :
A language over an alphabet is a set of strings over that alphabet. Therefore, a
language L is any subset of . That is, any is a language.

Example :

1. F is the empty language.

2. is a language for any .
3. {e} is a language for any . Note that, . Because the language F does
not contain any string but {e} contains one string of length zero.
4. The set of all strings over { 0, 1 } containing equal number of 0's and 1's.
5. The set of all strings over {a, b, c} that starts with a.

Convention : Capital letters A, B, C, L, etc. with or without subscripts are normally

used to denote languages.

Set operations on languages : Since languages are set of strings we can apply set
operations to languages. Here are some simple examples (though there is nothing new
in it).

Union : A string iff or

Example : { 0, 11, 01, 011 } { 1, 01, 110 } = { 0, 11, 01, 011, 111 }

Intersection : A string, xϵ L1 ∩ L2 iff x ϵ L1 and x ϵ L2 .

Example : { 0, 11, 01, 011 }{ 1, 01, 110 } = { 01 }

Complement : Usually, is the universe that a complement is taken with respect to.
Thus for a language L, the complement is L(bar) = { | }.

Example : Let L = { x | |x| is even }. Then its complement is the language { | |x|
is odd }.
Similarly we can define other usual set operations on languages like relative
complement, symmetric difference, etc.

Reversal of a language :
The reversal of a language L, denoted as , is defined as: .

Example :

1. Let L = { 0, 11, 01, 011 }. Then = { 0, 11, 10, 110 }.

8
 CS2303 THEORY OF COMPUTATION

2. Let L = { | n is an integer }. Then = { | n is an integer }.

Language concatenation : The concatenation of languages and is defined as

= { xy | and }.

Example : { a, ab }{ b, ba } = { ab, aba, abb, abba }.

Note that ,
1. in general.
2.
3.

Iterated concatenation of languages : Since we can concatenate two languages, we

also repeat this to concatenate any number of languages. Or we can concatenate a
language with itself any number of times. The operation denotes the concatenation of
L with itself n times. This is defined formally as follows:

Example : Let L = { a, ab }. Then according to the definition, we have

and so on.

Kleene's Star operation : The Kleene star operation on a language L, denoted as is

defined as follows :

= ( Union n in N )

= { x | x is the concatenation of zero or more strings from L }

9
 CS2303 THEORY OF COMPUTATION

Thus is the set of all strings derivable by any number of concatenations of strings
in L. It is also useful to define

= , i.e., all strings derivable by one or more concatenations of strings in L. That is

= (Union n in N and n >0)

=

Example : Let L = { a, ab }. Then we have,

= {e} {a, ab} {aa, aab, aba, abab} …

= {a, ab} {aa, aab, aba, abab} …

Note : ε is in , for every language L, including .

The previously introduced definition of is an instance of Kleene star.

(Generates) (Recognizes)
Grammar Language Automata

Automata: A algorithm or program that automatically recognizes if a particular string belongs to

the language or not, by checking the grammar of the string.

An automata is an abstract computing device (or machine). There are different varities
of such abstract machines (also called models of computation) which can be defined
mathematically.

Every Automaton fulfills the three basic requirements.

• Every automaton consists of some essential features as in real computers. It

has a mechanism for reading input. The input is assumed to be a sequence of
symbols over a given alphabet and is placed on an input tape(or written on an
input file). The simpler automata can only read the input one symbol at a time
from left to right but not change. Powerful versions can both read (from left to
right or right to left) and change the input.

10
 CS2303 THEORY OF COMPUTATION

• The automaton can produce output of some form. If the output in response to an
input string is binary (say, accept or reject), then it is called an accepter. If it
produces an output sequence in response to an input sequence, then it is called
a transducer(or automaton with output).
• The automaton may have a temporary storage, consisting of an unlimited
number of cells, each capable of holding a symbol from an alphabet ( whcih may
be different from the input alphabet). The automaton can both read and change
the contents of the storage cells in the temporary storage. The accusing
capability of this storage varies depending on the type of the storage.
• The most important feature of the automaton is its control unit, which can be
in any one of a finite number of interval states at any point. It can change state
in some defined manner determined by a transition function.

Figure 1: The figure above shows a diagrammatic representation of a

generic automation.

Operation of the automation is defined as follows.

At any point of time the automaton is in some integral state and is reading a particular
symbol from the input tape by using the mechanism for reading input. In the next time
step the automaton then moves to some other integral (or remain in the same state) as
defined by the transition function. The transition function is based on the current state,
input symbol read, and the content of the temporary storage. At the same time the
content of the storage may be changed and the input read may be modifed. The
automation may also produce some output during this transition. The internal state,
input and the content of storage at any point defines the configuration of the automaton
at that point. The transition from one configuration to the next ( as defined by the
transition function) is called a move. Finite state machine or Finite Automation is the
simplest type of abstract machine we consider. Any system that is at any point of time in
one of a finite number of interval state and moves among these states in a defined
manner in response to some input, can be modeled by a finite automaton. It doesnot
have any temporary storage and hence a restricted model of computation.

11
 CS2303 THEORY OF COMPUTATION

Finite Automata

Automata (singular : automation) are a particularly simple, but useful, model of

computation. They were initially proposed as a simple model for the behavior of
neurons.

States, Transitions and Finite-State Transition System :

Let us first give some intuitive idea about a state of a system and state transitions
before describing finite automata.

Informally, a state of a system is an instantaneous description of that system which

gives all relevant information necessary to determine how the system can evolve from
that point on.

Transitions are changes of states that can occur spontaneously or in response to

inputs to the states. Though transitions usually take time, we assume that state
transitions are instantaneous (which is an abstraction).

Some examples of state transition systems are: digital systems, vending machines, etc.

A system containing only a finite number of states and transitions among them is
called a finite-state transition system.

Finite-state transition systems can be modeled abstractly by a mathematical model

called finite automation

Deterministic Finite (-state) Automata

Informally, a DFA (Deterministic Finite State Automaton) is a simple machine that

reads an input string -- one symbol at a time -- and then, after the input has been
completely read, decides whether to accept or reject the input. As the symbols are read
from the tape, the automaton can change its state, to reflect how it reacts to what it has
seen so far. A machine for which a deterministic code can be formulated, and if there is
only one unique way to formulate the code, then the machine is called deterministic
finite automata.

Thus, a DFA conceptually consists of 3 parts:

1. A tape to hold the input string. The tape is divided into a finite number of cells.
Each cell holds a symbol from .
2. A tape head for reading symbols from the tape
3. A control , which itself consists of 3 things:
o finite number of states that the machine is allowed to be in (zero or
more states are designated as accept or final states),
o a current state, initially set to a start state,

12
 CS2303 THEORY OF COMPUTATION

o a state transition function for changing the current state.

An automaton processes a string on the tape by repeating the following actions until
the tape head has traversed the entire string:

1. The tape head reads the current tape cell and sends the symbol s found there to
the control. Then the tape head moves to the next cell.
2. he control takes s and the current state and consults the state transition
function to get the next state, which becomes the new current state.

Once the entire string has been processed, the state in which the automation enters is
examined. If it is an accept state , the input string is accepted ; otherwise, the string is
rejected . Summarizing all the above we can formulate the following formal definition:

Deterministic Finite State Automaton : A Deterministic Finite State Automaton (DFA) is

a 5-tuple :

• Q is a finite set of states.

• is a finite set of input symbols or alphabet
• is the “next state” transition function (which is total ). Intuitively,
is a function that tells which state to move to in response to an input, i.e., if M is
in state q and sees input a, it moves to state .
• is the start state.
• is the set of accept or final states.

Acceptance of Strings :

A DFA accepts a string if there is a sequence of states in

Q such that

1. is the start state.

2. for all .
3.

Language Accepted or Recognized by a DFA :

The language accepted or recognized by a DFA M is the set of all strings accepted by

M , and is denoted by i.e. The notion of

acceptance can also be made more precise by extending the transition function .

Extended transition function :

13
 CS2303 THEORY OF COMPUTATION

Extend (which is function on symbols) to a function on strings, i.e.

.

That is, is the state the automation reaches when it starts from the state q and
finish processing the string w. Formally, we can give an inductive definition as follows:

The language of the DFA M is the set of strings that can take the start state to one of
the accepting states i.e.

L(M) = { | M accepts w }

={ | }

Example 1 :

is the start state

It is a formal description of a DFA. But it is hard to comprehend. For ex. The language
of the DFA is any string over { 0, 1} having at least one 1

We can describe the same DFA by transition table or state transition diagram as
following:

Transition Table :

0 1

14
 CS2303 THEORY OF COMPUTATION

It is easy to comprehend the transition diagram.

Explanation : We cannot reach find state w/0 or in the i/p string. There can be any
no. of 0's at the beginning. ( The self-loop at on label 0 indicates it ). Similarly
there can be any no. of 0's & 1's in any order at the end of the string.

Transition table :

It is basically a tabular representation of the transition function that takes two

arguments (a state and a symbol) and returns a value (the “next state”).

• Rows correspond to states,

• Columns correspond to input symbols,
• Entries correspond to next states
• The start state is marked with an arrow
• The accept states are marked with a star (*).

0 1

(State) Transition diagram :

A state transition diagram or simply a transition diagram is a directed graph which can
be constructed as follows:

1. For each state in Q there is a node.

2. There is a directed edge from node q to node p labeled a iff . (If there
are several input symbols that cause a transition, the edge is labeled by the list of
these symbols.)
3. There is an arrow with no source into the start state.
4. Accepting states are indicated by double circle.

15
 CS2303 THEORY OF COMPUTATION

5.
6. Here is an informal description how a DFA operates. An input to a DFA can be
any string . Put a pointer to the start state q. Read the input string w from
left to right, one symbol at a time, moving the pointer according to the transition
function, . If the next symbol of w is a and the pointer is on state p, move the
pointer to . When the end of the input string w is encountered, the pointer is
on some state, r. The string is said to be accepted by the DFA if and rejected if
. Note that there is no formal mechanism for moving the pointer.
7. A language is said to be regular if L = L(M) for some DFA M.

Regular Expressions: Formal Definition

We construct REs from primitive constituents (basic elements) by repeatedly applying

certain recursive rules as given below. (In the definition)

Definition : Let S be an alphabet. The regular expressions are defined recursively

as follows.

Basis :

i) is a RE

ii) is a RE

iii) , a is RE.

These are called primitive regular expression i.e. Primitive Constituents

Recursive Step :

If and are REs over, then so are

i)

ii)

16
 CS2303 THEORY OF COMPUTATION

iii)

iv)

Closure : r is RE over only if it can be obtained from the basis elements

(Primitive REs) by a finite no of applications of the recursive step (given in 2).

Example : Let = { 0,1,2 }. Then (0+21)*(1+ F ) is a RE, because we can construct

this expression by applying the above rules as given in the following step.
Steps RE Constructed Rule Used
1 1 Rule 1(iii)
2 Rule 1(i)
3 1+ Rule 2(i) & Results of Step 1, 2
4 (1+ ) Rule 2(iv) & Step 3
5 2 1(iii)
6 1 1(iii)
7 21 2(ii), 5, 6
8 0 1(iii)
9 0+21 2(i), 7, 8
10 (0+21) 2(iv), 9
11 (0+21)* 2(iii), 10
12 (0+21)* 2(ii), 4, 11
Language described by REs : Each describes a language (or a language is
associated with every RE). We will see later that REs are used to attribute regular
languages.

Notation : If r is a RE over some alphabet then L(r) is the language associate with r .
We can define the language L(r) associated with (or described by) a REs as follows.

1. is the RE describing the empty language i.e. L( )= .

2. is a RE describing the language { } i.e. L( )={ }.

3. , a is a RE denoting the language {a} i.e . L(a) = {a} .

4. If and are REs denoting language L( ) and L( ) respectively, then

i) is a regular expression denoting the language L( ) = L( ) ∪ L( )

17
 CS2303 THEORY OF COMPUTATION

ii) is a regular expression denoting the language L( )=L( ) L( )

iii) is a regular expression denoting the language

iv) ( ) is a regular expression denoting the language L(( )) = L( )

Example : Consider the RE (0*(0+1)). Thus the language denoted by the RE is

L(0*(0+1)) = L(0*) L(0+1) .......................by 4(ii)

= L(0)*L(0) ∪ L(1)

={ , 0,00,000,........} {0} {1}

={ , 0,00,000,........} {0,1}

= {0, 00, 000, 0000,..........,1, 01, 001, 0001,...............}

Precedence Rule

Consider the RE ab + c. The language described by the RE can be thought of either

L(a)L(b+c) or L(ab) L(c) as provided by the rules (of languages described by REs)
given already. But these two represents two different languages lending to ambiguity.
To remove this ambiguity we can either

1) Use fully parenthesized expression- (cumbersome) or

2) Use a set of precedence rules to evaluate the options of REs in some order.
Like other algebras mod in mathematics.

For REs, the order of precedence for the operators is as follows:

i) The star operator precedes concatenation and concatenation precedes union (+)
operator.

ii) It is also important to note that concatenation & union (+) operators are
associative and union operation is commutative.

Using these precedence rule, we find that the RE ab+c represents the language
L(ab) L(c) i.e. it should be grouped as ((ab)+c).

We can, of course change the order of precedence by using parentheses. For

example, the language represented by the RE a(b+c) is L(a)L(b+c).

18
 CS2303 THEORY OF COMPUTATION

Example : The RE ab*+b is grouped as ((a(b*))+b) which describes the language

L(a)(L(b))* L(b)

Example : The RE (ab)*+b represents the language (L(a)L(b))* L(b).

Example : It is easy to see that the RE (0+1)*(0+11) represents the language of all
strings over {0,1} which are either ended with 0 or 11.

Example : The regular expression r =(00)*(11)*1 denotes the set of all strings with an
even number of 0's followed by an odd number of 1's i.e.

Note : The notation is used to represent the RE rr*. Similarly, represents the RE
rr, denotes r, and so on.

An arbitrary string over = {0,1} is denoted as (0+1)*.

Exercise : Give a RE r over {0,1} s.t. L(r)={ has at least one pair
of consecutive 1's}

Solution : Every string in L(r) must contain 00 somewhere, but what comes before
and what goes before is completely arbitrary. Considering these observations we can
write the REs as (0+1)*11(0+1)*.

Example : Considering the above example it becomes clean that the RE

(0+1)*11(0+1)*+(0+1)*00(0+1)* represents the set of string over {0,1} that contains
the substring 11 or 00.

Example : Consider the RE 0*10*10*. It is not difficult to see that this RE describes the
set of strings over {0,1} that contains exactly two 1's. The presence of two 1's in the
RE and any no of 0's before, between and after the 1's ensure it.

Example : Consider the language of strings over {0,1} containing two or more 1's.

Solution : There must be at least two 1's in the RE somewhere and what comes before,
between, and after is completely arbitrary. Hence we can write the RE as
(0+1)*1(0+1)*1(0+1)* . But following two REs also represent the same language, each
ensuring presence of least two 1's somewhere in the string

i) 0*10*1(0+1)*

ii) (0+1)*10*10*

Example : Consider a RE r over {0,1} such that

19
 CS2303 THEORY OF COMPUTATION

L(r) = { has no pair of consecutive 1's}

Solution : Though it looks similar to ex ……., it is harder to construct to construct.

We observer that, whenever a 1 occurs, it must be immediately followed by a 0. This
substring may be preceded & followed by any no of 0's. So the final RE must be a
repetition of strings of the form: 00…0100….00 i.e. 0*100*. So it looks like the RE is
(0*100*)*. But in this case the strings ending in 1 or consisting of all 0's are not
accounted for. Taking these observations into consideration, the final RE is r =
(0*100*)(1+ )+0*(1+ ).

Alternative Solution :

The language can be viewed as repetitions of the strings 0 and 01. Hence get the RE as
r = (0+10)*(1+ ).This is a shorter expression but represents the same language.

Regular Expression and Regular Language :

Equivalence(of REs) with FA :

Recall that, language that is accepted by some FAs are known as Regular language.
The two concepts : REs and Regular language are essentially same i.e. (for) every
regular language can be developed by (there is) a RE, and for every RE there is a
Regular Langauge. This fact is rather suprising, because RE approach to describing
language is fundamentally differnet from the FA approach. But REs and FA are
equivalent in their descriptive power. We can put this fact in the focus of the following
Theorem.

Theorem : A language is regular iff some RE describes it.

This Theorem has two directions, and are stated & proved below as a separate lemma

RE to FA :

REs denote regular languages :

Lemma : If L(r) is a language described by the RE r, then it is regular i.e. there is a FA

such that L(M) L(r).

Proof : To prove the lemma, we apply structured index on the expression r. First, we
show how to construct FA for the basis elements: , and for any . Then we show
how to combine these Finite Automata into Complex Automata that accept the Union,
Concatenation, Kleen Closure of the languages accepted by the original smaller
automata.

20
 CS2303 THEORY OF COMPUTATION

Use of NFAs is helpful in the case i.e. we construct NFAs for every REs which
are represented by transition diagram only.

Basis :

• Case (i) : . Then . Then and the following NFA

N recognizes L(r). Formally where Q = {q}
and .

• Case (ii) : . , and the following NFA N accepts L(r). Formally

where .

Since the start state is also the accept step, and there is no any transition defined, it
will accept the only string and nothing else.

• Case (iii) : r = a for some . Then L(r) = {a}, and the following NFA
N accepts L(r).

Formally, where for or

Induction :

21
 CS2303 THEORY OF COMPUTATION

Assume that the start of the theorem is true for REs and . Hence we can assume
that we have automata and that accepts languages denoted by REs and ,
respectively i.e. and . The FAs are
represented schematically as shown below.

Each has an initial state and a final state. There are four cases to consider.

• Case (i) : Consider the RE denoting the language .

We construct FA , from and to accept the language denoted by
RE as follows :

Create a new (initial) start state and give - transition to the initial state of and
.This is the initial state of .

• Create a final state and give -transition from the two final state of
and . is the only final state of and final state of and will be
ordinary states in .
• All the state of and are also state of .
22
 CS2303 THEORY OF COMPUTATION

 All the moves of and are also moves of . [ Formal Construction]

It is easy to prove that

Proof: To show that we must show that

= by following transition of

Starts at initial state and enters the start state of either or follwoing the
transition i.e. without consuming any input. WLOG, assume that, it enters the start state
of . From this point onward it has to follow only the transition of to enter the final
state of , because this is the only way to enter the final state of M by following the
e-transition.(Which is the last transition & no input is taken at hte transition). Hence the
whole input w is considered while traversing from the start state of to the final
state of . Therefore must accept .

Say, or .

WLOG, say

Therefore when process the string w , it starts at the initial state and enters the final
state when w consumed totally, by following its transition. Then also accepts w, by
starting at state and taking -transition enters the start state of -follows the moves
of to enter the final state of consuming input w thus takes -transition to
. Hence proved

• Case(ii) : Consider the RE denoting the language . We

construct FA from & to accept as follows :
23
 CS2303 THEORY OF COMPUTATION

Create a new start state and a new final state

1. Add - transition from

o to the start state of
o to
o final state of to the start state of
2. All the states of are also the states of . has 2 more states than that
of namely and .
3. All the moves of are also included in .

By the transition of type (b), can accept .

By the transition of type (a), can enters the initial state of w/o any input and then
follow all kinds moves of to enter the final state of and then following -transition
can enter . Hence if any is accepted by then w is also accepted by . By the
transition of type (b), strings accepted by can be repeated by any no of times & thus
accepted by . Hence accepts and any string accepted by repeated (i.e.

concatenated) any no of times. Hence

Case(iv) : Let =( ). Then the FA is also the FA for ( ), since the use of
parentheses does not change the language denoted by the expression

Non-Deterministic Finite Automata

Nondeterminism is an important abstraction in computer science. Importance of
nondeterminism is found in the design of algorithms. For examples, there are many
problems with efficient nondeterministic solutions but no known efficient deterministic
solutions. ( Travelling salesman, Hamiltonean cycle, clique, etc). Behaviour of a process
is in a distributed system is also a good example of nondeterministic situation. Because
24
 CS2303 THEORY OF COMPUTATION

the behaviour of a process might depend on some messages from other processes
that might arrive at arbitrary times with arbitrary contents.
It is easy to construct and comprehend an NFA than DFA for a given regular
language. The concept of NFA can also be used in proving many theorems and
results. Hence, it plays an important role in this subject.
In the context of FA nondeterminism can be incorporated naturally. That is, an NFA is
defined in the same way as the DFA but with the following two exceptions:
• multiple next state.

• - transitions.

Multiple Next State :

• In contrast to a DFA, the next state is not necessarily uniquely determined by

the current state and input symbol in case of an NFA. (Recall that, in a DFA
there is exactly one start state and exactly one transition out of every state for
each symbol in ).
• This means that - in a state q and with input symbol a - there could be one, more
than one or zero next state to go, i.e. the value of is a subset of Q. Thus
= which means that any one of could be the next
state.
• The zero next state case is a special one giving = , which means that
there is no next state on input symbol when the automata is in state q. In such a
case, we may think that the automata "hangs" and the input will be rejected.

- transitions :

In an -transition, the tape head doesn't do anything- it doesnot read and it doesnot move.
However, the state of the automata can be changed - that is can go to zero, one
or more states. This is written formally as implying that the next
state could by any one of w/o consuming the next input symbol.

Acceptance :

Informally, an NFA is said to accept its input if it is possible to start in some start state
and process , moving according to the transition rules and making choices along the way
whenever the next state is not uniquely defined, such that when is completely processed
(i.e. end of is reached), the automata is in an accept state. There may be several
possible paths through the automation in response to an input since the start state is not
determined and there are choices along the way because of multiple next states. Some of
these paths may lead to accpet states while others may not. The
25
 CS2303 THEORY OF COMPUTATION

automation is said to accept if at least one computation path on input starting from at
least one start state leads to an accept state- otherwise, the automation rejects input
. Alternatively, we can say that, is accepted iff there exists a path with label from
some start state to some accept state. Since there is no mechanism for determining which
state to start in or which of the possible next moves to take (including the - transitions) in
response to an input symbol we can think that the automation is having some "guessing"
power to chose the correct one in case the input is accepted

Example 1 : Consider the language L = { {0, 1}* | The 3rd symbol from the right
is 1}. The following four-state automation accepts L.

The m/c is not deterministic since there are two transitions from state on input 1 and
no transition (zero transition) from on both 0 & 1.

For any string whose 3rd symbol from the right is a 1, there exists a sequence of legal
transitions leading from the start state q, to the accept state . But for any string
where 3rd symbol from the right is 0, there is no possible sequence of legal
tranisitons leading from and . Hence m/c accepts L. How does it accept any string
L?

Formal definition of NFA :

Formally, an NFA is a quituple where Q, , , and F bear

the same meaning as for a DFA, but , the transition function is redefined as follows:

where P(Q) is the power set of Q i.e. .

The Langauge of an NFA :

From the discussion of the acceptance by an NFA, we can give the formal definition of a
language accepted by an NFA as follows :

If is an NFA, then the langauge accepted by N is writtten as L(N) is

given by .

That is, L(N) is the set of all strings w in such that contains at least one
accepting state.

26
 CS2303 THEORY OF COMPUTATION

Removing ϵ-transition:
- transitions do not increase the power of an NFA . That is, any - NFA ( NFA with
transition), we can always construct an equivalent NFA without -transitions. The
equivalent NFA must keep track where the NFA goes at every step during
computation. This can be done by adding extra transitions for removal of every -
transitions from the - NFA as follows.

If we removed the - transition from the - NFA , then we need to moves

from state p to all the state on input symbol which are reachable from state q (in
the - NFA ) on same input symbol q. This will allow the modified NFA to move from
state p to all states on some input symbols which were possible in case of -NFA on
the same input symbol. This process is stated formally in the following theories.

Theorem if L is accepted by an - NFA N , then there is some equivalent

without transitions accepting the same language L
Proof:

Let be the given with

We construct

Where, for all and and

Other elements of N' and N

We can show that i.e. N' and N are equivalent.

We need to prove that

i.e.

We will show something more, that is,

27
 CS2303 THEORY OF COMPUTATION

We will show something more, that is,

Basis : , then

But by definition of .

Induction hypothesis Let the statement hold for all with .

By definition of extension of

By inductions hypothesis.

Assuming that

By definition of

Since

To complete the proof we consider the case

When i.e. then

28
 CS2303 THEORY OF COMPUTATION

and by the construction of wherever constrains a state in F.

If (and thus is not in F ), then with leads to an accepting state in N' iff it
lead to an accepting state in N ( by the construction of N' and N ).

Also, if ( , thus w is accepted by N' iff w is accepted by N (iff )

If (and, thus in M we load in F ), thus is accepted by both N' and N .

Let . If w cannot lead to in N , then . (Since can add transitions to get an accept
state). So there is no harm in making an accept state in N'.

Ex: Consider the following NFA with - transition.

Transition Diagram

0 1

Transition diagram for ' for the equivalent NFA without - moves

29
 CS2303 THEORY OF COMPUTATION

0 1

Since the start state q0 must be final state in the equivalent NFA .

Since and and we add moves and

in the equivalent NFA . Other moves are also constructed accordingly.

-closures:

The concept used in the above construction can be made more formal by defining the
-closure for a state (or a set of states). The idea of -closure is that, when moving
from a state p to a state q (or from a set of states Si to a set of states Sj ) an input
, we need to take account of all -moves that could be made after the transition.
Formally, for a given state q,

-closures:

Similarly, for a given set

-closures:

So, in the construction of equivalent NFA N' without -transition from any NFA with

moves. the first rule can now be written as

30
 CS2303 THEORY OF COMPUTATION

Equivalence of NFA and DFA

It is worth noting that a DFA is a special type of NFA and hence the class of languages
accepted by DFA s is a subset of the class of languages accepted by NFA s.
Surprisingly, these two classes are in fact equal. NFA s appeared to have more power
than DFA s because of generality enjoyed in terms of -transition and multiple next
states. But they are no more powerful than DFA s in terms of the languages they
accept.

Converting DFA to NFA

Theorem: Every DFA has as equivalent NFA

Proof: A DFA is just a special type of an NFA . In a DFA , the transition functions is
defined from whereas in case of an NFA it is defined from and
be a DFA . We construct an equivalent NFA
as follows.

i. e

If and

All other elements of N are as in D.

If then there is a sequence of states such that

Then it is clear from the above construction of N that there is a sequence of states (in N)

such that and and hence

Similarly we can show the converse.

Hence ,

Given any NFA we need to construct as equivalent DFA i.e. the DFA need to simulate
the behaviour of the NFA . For this, the DFA have to keep track of all the states where
the NFA could be in at every step during processing a given input string.

31
 CS2303 THEORY OF COMPUTATION

There are possible subsets of states for any NFA with n states. Every subset
corresponds to one of the possibilities that the equivalent DFA must keep track of. Thus,
the equivalent DFA will have states.

The formal constructions of an equivalent DFA for any NFA is given below. We
first consider an NFA without transitions and then we incorporate the affects of
transitions later.

Formal construction of an equivalent DFA for a given NFA without transitions.

Given an without - moves, we construct an equivalent DFA

as follows

i.e.

(i.e. every subset of Q which as an element in F is considered as a final stat

in DFA D )

for all and

where

That is,

To show that this construction works we need to show that L(D)=L(N) i.e.

Or,

We will prove the following which is a stranger statement thus required.

32
 CS2303 THEORY OF COMPUTATION

Proof : We will show by inductions on

Basis If =0, then w =

So, by definition.

Inductions hypothesis : Assume inductively that the statement holds of length

less than or equal to n.

Inductive step

Let , then with

Now,

Now, given any NFA with -transition, we can first construct an equivalent NFA without
-transition and then use the above construction process to construct an equivalent
DFA , thus, proving the equivalence of NFA s and DFA s..

It is also possible to construct an equivalent DFA directly from any given NFA with -
transition by integrating the concept of -closure in the above construction.

Recall that, for any

- closure :

33
 CS2303 THEORY OF COMPUTATION

In the equivalent DFA , at every step, we need to modify the transition functions to
keep track of all the states where the NFA can go on -transitions. This is done by

replacing by -closure , i.e. we now compute at every step as

follows:

Besides this the initial state of the DFA D has to be modified to keep track of all the
states that can be reached from the initial state of NFA on zero or more -transitions.
This can be done by changing the initial state to -closure ( ).
It is clear that, at every step in the processing of an input string by the DFA D , it enters
a state that corresponds to the subset of states that the NFA N could be in at that
particular point. This has been proved in the constructions of an equivalent NFA for any
-NFA
If the number of states in the NFA is n , then there are states in the DFA . That
is, each state in the DFA is a subset of state of the NFA .
But, it is important to note that most of these states are inaccessible from the start state
and hence can be removed from the DFA without changing the accepted language. Thus,
in fact, the number of states in the equivalent DFA would be much less
than .
Example : Consider the NFA given below.

0 1

{ }

Since there are 3 states in the NFA

34
 CS2303 THEORY OF COMPUTATION

There will be states (representing all possible subset of states) in the

equivalent DFA . The transition table of the DFA constructed by using the subset
constructions process is produced here.

0 1 The start state of the DFA is - closures

The final states are all those subsets that contains

(since in the NFA).

Let us compute one entry,
{ }

Similarly, all other transitions can be computed

0 1

Corresponding Transition fig. for DFA.Note that states

are not accessible and hence can be removed. This

gives us the following simplified DFA with only 3 states.
35
 CS2303 THEORY OF COMPUTATION

It is interesting to note that we can avoid encountering all those inaccessible

or unnecessary states in the equivalent DFA by performing the following two
steps inductively.

1. If is the start state of the NFA, then make - closure ( ) the start state of
the equivalent DFA . This is definitely the only accessible state.
2. If we have already computed a set of states which are accessible. Then

. compute because these set of states will also be accessible.

Following these steps in the above example, we get the transition table given below

36
CS2303 THEORY OF COMPUTATION