UNIT I

AUTOMATA FUNDAMENTALS

1.1 Introduction to Automata theory

Automata theory is the study of abstract machines and the computational problems
can be solved using these machines. Abstract machines are called automata. The name
comes from the Greek word (Αυτόματα).

It means doing something by itself. An automaton can be a finite representation of

a formal language that may be an infinite set. Automata are used as theoretical models for
computing machines, and are used for proofs about computability. The automata theory
is essential for,

++ The study of the limits of computation

++ Designing and checking the behaviour of digital circuits.

++ Pattern searching in Websites

++ Verifying systems of all types that have a finite number of distinct states, such as
communications protocols or protocols for secure exchange information

1.1.1 Introduction to Formal Languages

Formal languages are the system used to train the machines in recognizing certain
commands or instructions. These languages are the abstraction of natural languages,
since they are expended by the machines. Formal languages are of five types. They are:

rr Regular Languages (RL)

rr Context free Languages (CFL)

rr Context Sensitive Languages (CSL)

1.2 Theory of Computation

rr Recursive Languages

rr Recursively Enumerable Languages (RE)

àà These languages are recognized by specific automata/machines and grammars.

rr Regular grammars (type 3) and finite automata recognize regular

languages.

rr Context free grammars (Type 2) and push down automata recognize

context free languages.

rr Context sensitive grammars (Type 1) and Linear Bounded Automata

(LBA) recognize context sensitive languages.

rr Unrestricted grammars (phrase structure grammar) (Type 0).

rr Turing machines recognize recursively enumerable languages.

àà Total Turing Machines (TTM) that halt for every input are used to recognize
recursive languages.

1. Formal Language Theory

Formal language theory describes languages as a set of operations over an alphabet.

It is closely linked with automata theory, as automata are used to generate and recognize
formal languages. Automata are used as models for computation; formal languages are
the preferred mode of specification for any problem that must be computed.

2. Computability theory

Computability theory deals primarily with the question of the extent to which a
problem is solvable on a computer. It is closely related to the branch of mathematical
logic called recursion theory.

3. Models of Computation

The computation models that are developed by formal language theory are ,

i) Finite State Automata

ii) Regular expression

Automata Fundamentals 1.3

iii) Push down Automata

iv) Linear bounded automata

v) Turing machine

àà The computational models and the languages understandable by these models are
tabulated below.

Table 1.1 The Computational Models

Machines Grammars/ Languages Category

Finite State Automata

Regular Type 3 Simple
(Regular Expression)
Push Down Automata Context Free Type 2

Linear Bounded Automata Context Sensitive Type 1

Turing Machine Phrase Structure Type 0 Complex

Uncomputable

1.1.2 Basic Mathematical Notation and Techniques

1. Alphabet

An alphabet is a finite, nonempty set of symbols.

Example:

i. ∑ ={0,1}

ii. ∑ ={a,b,c}

2. String

A string over an alphabet is a finite sequence of symbols from that alphabet.

1.4 Theory of Computation

Example:

i. 01001 over ∑ ={0,1}

ii. aaabbbbccc over ∑ ={a,b,c}

3. Length of a string

The length of a string is the count of symbols in that string.

Example:

i. |01001| = 5

ii. |aaabbbbccc| =10

iii. |0315| = 8

4. Power of an alphabet

The power of an alphabet ∑k, is the set of all strings over ∑ with length k.

Examples:

∑ = {0,1}
∑ 2 = {00, 01, 10, 11}
∑ 3 = {000, 001, 010, 011,100,101,110,111}
……………..
∑* = {e, 0,1, 00, 01,10,11, 000, 001, 010, 011,100,101,110,111……………}
= Σ 0 ∪ Σ1 ∪ Σ 2 .......................
= Σ0 ∪ Σ+
∑ + = {0,1, 00, 01,10,11, 000, 001, 010, 011,100,101,110,111……………}
= Σ1 ∪ Σ 2 ∪ Σ 3 .......................

5. Language (L)

The language of an Automata is a set of strings accepted by the automata.

Automata Fundamentals 1.5

Examples:

i. Set of even length strings over an alphabet {a,b}.

ii. Set of odd length strings over an alphabet {0,1}.

6. Set –former notation of a Language

i. L={w |w consists of an equal number of 0’s and 1’s }

L={ε, 01, 10,0011, 1100, 0101, 1010, 1001, 0110,………}

ii. L= {w |w is a binary integer that is prime }

L={10, 11, 101, 111, …….}

7. Complement of a Language( L )

i. L={w |w contains 101 as substring}

Ḹ ={w |w does not contain 101}

ii. L={w |w contains abb as substring}

L ={w |w does not contain abb}

1.2 Introduction to Formal Proof

A formal proof or derivation is a finite sequence of sentences called well-formed

formulas in the case of a formal language each of which is an axiom or follows from the
preceding sentences in the sequence by a rule of inference. But in deductive proofs, the
truth of a statement is shown by a detailed sequence of steps and reasons.

Some computer scientists take the extreme view that a formal proof of the
correctness of a program should go hand-in-hand with the writing of the program itself.
We doubt that doing so is productive. Some also say that proof has no place in the
discipline of programming.

++ The slogan “if you are not sure your program is correct, run it and see” is commonly
offered by them.
1.6 Theory of Computation

++ Testing programs is surely essential. However, testing goes only so far, since you
cannot try your program on every input.

++ To make your iteration or recursion correct, you need to set up an inductive

hypothesis, and it is helpful to reason, formally or informally, that the hypothesis
is consistent with the iteration or recursion.

++ This process of understanding the workings of a correct program is essentially the

same as the process of proving theorems by induction.

++ Automata theory covers methodologies of formal proof. It can be of either :

➢➢ Inductive kind

Recursive proofs of a parameterized statement that use the statement itself with
lower values of the parameter.

➢➢ Deductive kind

A sequence of justified steps.

1.2.1 Deductive Proofs

àà A deductive proof consists of a sequence of statements whose truth leads us

from some initial statement, called the hypothesis or the given statement(s), to a
conclusion statement.

àà Each step in the proof must follow, by some accepted logical principle, from either
the given facts, or some of the previous statements in the deductive proof, or a
combination of these.

àà The hypothesis may be true or false, typically depending on values of its parameters.
Often, the hypothesis consists of several independent statements connected by a
logical AND.

àà The theorem that is proved when we go for a hypothesis H to a conclusion C is the

statement “if H then C”. We say that C is deduced from H.

àà An example theorem of the form “if H then C” will illustrate these points.
Automata Fundamentals 1.7

Theorem 1
If x ≥ 4, then 2x ≥ x2.
Proof
The hypothesis H is “x ≥ 4”. This hypothesis has a parameter, x and thus is neither
true nor false. Rather, its truth depends on the value of x.

H is true for x = 6 and false for x = 2.

àà The conclusion C is “2x ≥ x2”. This statement also uses parameter x and is true for
certain values of x and not others.

Example:

C is false for x = 3, since 23 = 8, which is not as large as 32 = 9. On the other hand,

C is true for x = 4, since 24 = 42 = 16. For x = 5, the statement is also true, since 25 = 32 is
at least as large as 52 = 25.

Perhaps you can see the intuitive argument that tells us the conclusion 2x= x2 will
be true whenever x ≥ 4. We already saw that it is true for x = 4. As x grows larger than 4,
the left side, 2x doubles each time x increases by 1.

However, the right side, x2, grows by the ratio (x+1/x)2.

If x ≥ 4, then (x + 1)/x cannot be greater than 1.25, and therefore (x+1/x)2 =

(1.25)2 = 1.5625.

Since 1.5625 < 2, each time x increases above 4 the left side 2x grows more than
the right side x2.

^^ Thus, as long as we start from a value like x = 4 the inequality 2x ≥ x2 is already

satisfied.

Theorem 2
If x is the sum of the squares of four positive integers, then 2x ≥ x2.
Proof
In deductive proof, we go from a hypothesis H to a conclusion C, i.e., if H then C.
1.8 Theory of Computation

Step 1:
x is the sum of the squares of four integers. Let a, b, c, d be four integers.
x = a2 + b2 + c2 + d2
Step 2:
The integers being squared are at least 1.
a ≥ 1; b ≥ 1; c ≥ 1; d ≥ 1.
Step 3:
Since the integers is at least 1, then its squares is also at least 1.
a2 ≥ 1; b2 ≥ 1; c2 ≥1; d2 ≥ 1
Step 4:
From Step 1 and Step 3, we can inter that x is sum of four squares and each
squares is at least 1. x is at least 1+1+1+1 x ≥ 4.
Step 5:
Step 4 is the hypothesis of the previous problem (2x ≥ x2 if x ≥ 4). We can conclude
that,
2x ≥ x2 (or) a2 + b2 + c2 + d2

1.2.2 Reduction to Definitions

If the hypothesis does not use familiar terms like integer, multiplication, addition
etc., then we can convert all terms in the hypothesis to their definitions.

Theorem 3
A set S is finite if there exists an integer n such that S has exactly n elements. |S| = n.
Where,

n - Number of elements in the set S.

S and T - Both subsets of some infinite set U.

T - Complement of S (with respect to U) if S U T = U and S ∩ T = Ф

T - Infinite.
Automata Fundamentals 1.9

Proof
We can use proof by contradiction. It is a technique where we assume that the
conclusion is false. Then use that assumption together with hypothesis, prove the opposite
of one of the given statements of the hypothesis. So the only possibility that remains is
that the conclusion is true whenever the hypothesis is true.

Here T is finite (because we assume the conclusion is false), but T is infinite .

Given
Let us assume T is finite, along with the statement of the hypothesis, S is finite.
i.e., |S| = n for some integer n. |T| = m for some integer m.

Now given statement tells us that S U T = |S| + |T| = n+m, n+m is a integer it
follows U is finite. But it contradicts the given statement U is infinite.

So the conclusion is true whenever the hypothesis is true. Therefore T is infinite.

1.2.3 Other Theorem Forms

1. If - then

àà The most common forms of if - then statements are if H then C can be rewritten as

i. H implies C

ii. H only if C

iii. C if H

iv. Whenever H holds, C follows.

àà So the theorem if x ≥ 4, 2x = x2 can be rewritten as

(a) x ≥ 4, implies 2x = x2

(b) x ≥ 4 only if 2x = x2

(c) 2x = x2 if x ≥ 4

(d) Whenever x ≥ 4 holds, 2x = x2 follows.

1.10 Theory of Computation

2. If - and - only - if statements

The statements of the form “A if and only if B” or “Aiff B” has two if - then
statements, is “if A then B” and “if B then A”.

Note:

└x┘- Floor of real number x, is the greatest integer equal to or less than x.

┌x┐- Ceiling of real number x, is the least integer equal to or greater than x.

Theorem 4

Let x be a real number. Then └x┘= ┌x┐, if and only if x is an integer.

Proof

└x┘≤ x by definition of floor ... (1.1)

┌x┐≥ x by definition of ceiling ... (1.2)

We are given with └x┘= ┌x┐

Substituting (1.1) in (1.2), we get,

┌x┐≤ x.

Since ┌x┐≥ x, by arithmetic inequality we get

┌x┐ = x.

3. Theorems that appear “Not to be if-then statements.

Theorem 5

Sin2ɵ¸ + Cos2ɵ = 1.

It does not have any hypothesis. This theorem can be written in if-then is “if ɵ¸ is
an angle, then sin2ɵ + cos2ɵ = 1”.
Automata Fundamentals 1.11

1.3 ADDITIONAL FORMS OF PROOF

The following are the additional forms of proofs.

rr Proofs about sets

rr Proofs by contradiction

rr Proofs by counter example

1.3.1 Proofs About Sets

àà Sets contain symbols to form character strings.

àà Sets in automata theory are called as languages.

If E and F are two expressions representing sets, the statement E = F means that
two sets represented are same. i.e., every element in the set represented by E is in the set
represented by F and vice versa.

Example:
Union of sets obeys commutative law. Let S and R be sets. Then R U S = S U R. If
E is the expression in R U S and F is the expression S U R, then E = F, an element
x is in E iff x is in F.

Theorem 6

Distributive law of union over intersection. Let R, S, T be sets. Then prove that

R U (S ∩ T) = (R U S) ∩ (R U T)

Proof

Aiff B has two parts. That are,

rr If part: “if B then A”

rr Only if part: if A then B, which is equivalent form “A only if B”.

Let E is the expression in R ∩ (S U T) and F is the expression in (R U S) ∩ (R U T).

1.12 Theory of Computation

1.. If part: if x is in E, x is in F

Statement Justification

(a) x is in R ∩ (S U T) (a) Given

(b) x is in R or x is in (S ∩ T) (a) and definition of union.

(c) x is in R or x is in both S and T (b) and definition of intersection.

(d) x is in R U S (c) and definition of union.

(e) x is in R U T (c) and definition of union.

(f) x is in (R U S) ∩ (R U T) (d), (c) and definition of intersection.

2. We can also prove it by “only – if” statement.

Statement Justification

(a) x is in (R U S) ∩ (R U T) Given

(b) x is in R U S (a) and definition of intersection.

(c) x is in R U T (a) and definition of intersection.

(d) x is inR or x is in both S and T (b), (c) and reasoning about unions.

(e) x is in R or x is in S ∩ T (d) and definition of intersections.

(f) x is in R U (S ∩ T) (e) and definition of union.

Example:
“if x ≥ 4, then 2x ≥ x2”. Then the contrapositive of this statement is “if not 2x ≥
x2, then not x ≥ 4”. It is otherwise “not a ≥ b” is equal to a < b.

not x ≥ 4 is x<4

not 2x ≥ x2 is 2x< x2.

i.e., “if 2x< x2, then x < 4”
Automata Fundamentals 1.13

1.3.2 Proof by Contradiction

1. It is derived from Latin meaning reduction to the “absurd”.

2. In proof by contradiction, we assume that the theorem is false and then

show that this assumption leads to an obviously false consequence, called
a contradiction.

3. Another way to prove a statement of the form “if H then C” is to prove the
statement “H and not C implies falsehood”.
Step 1:
State by assuming both the hypothesis H and the negation of the conclusion C.

Step 2:
Compute the proof by showing that something known to be false follows logically
from H and C. This form of proof is called proof by contradiction.

Example:
Jack Sees Jill, who has just come in from outdoors. On observing that she is
completely dry, he knows that it is not raining.

Proof

His proof = that it is not raining

Assume the negation of conclusion, ie, it is raining, then Jill would be wet. But
she is not wet, so it must not be raining.

Theorem 7

Let S be a finite subset of some infinite set U. Let T be complement of S with

respect to U. Then T is infinite.

Proof
H = S is finite set of U

U is an infinite set

T is the complement of S with respect to U.

1.14 Theory of Computation

Conclusion C = “T is infinite”

^^ We proceed to prove the theorem by proof by contradiction.

^^ We assume not C is true. T is finite.

From the assumption S is finite, if T is also finite, then U = S U T is also finite. But
hypothesis says U is infinite. Therefore the logical statement is false.

1.3.3 Proofs by Counter Examples

It is an exception to a proposition general rule. i.e. Specific instance of the falsity

of a universal quantification.

Example:

The statement “all students are lazy”.

Proof
Counter example, a hardworking diligent student counters the statement.

Theorem 8

All primes are odd.

Proof
The integer 2 is prime, but 2 is even.

Theorem 9

There is no pair of integers a and b such that a mod b = b mod a.

Proof

Let us assume a < b.

a mod b = a a = qb + r

a = 0 x b + a. q = quotient r = remainder.

But b mod a < a, is between 0 - 1. Thus when a < b, b mod a < a mod b, so a mod
b = b mod a is impossible. It is same argument for a > b also.
Automata Fundamentals 1.15

Consider a = b. a mod b = b mod a = 0 ( x mod x = 0 ) by counter example, let us

take a = b = 2, a mod b = b mod a = 0 i.e., 2 mod 2 = 2 mod 2 = 0.

1.4 INDUCTIVE PROOFS

1.4.1 Induction on Integers

Proof by Induction is a technique by which the truth of a number of statements

can be inferred from the truth of a few specific instances. Suppose, let P(n) be a statement
about a non-negative integer n. The principle of mathematical induction is that P(n)
follows from:

rr P(1)

rr P (n-1) implies P(n) for all n ≥ 1.

Condition (a) is called basis and the condition (b) is called inductive step, because
it connects Pn with Pn+1.

1.4.2 Structural Inductions

àà In automata theory, there are several recursively defined structures about which we
need to prove statements.

àà The examples are trees and expressions.

àà Like inductions, all recursive definitions have a basis case, where one or more
elementary structures are defined, and an inductive step, where more complex
structures are defined in terms of previously defined structures.

àà Structural induction is a proof method that is used in mathematical logic, computer

science, graph theory, and some other mathematical fields. It is a generalization of
mathematical induction.

àà A recursive definition or inductive definition is one that defines something in terms

of itself (that is, recursively), in a useful way.

Example:

Let us take expressions using the arithmetic operators + and *, with both numbers
and variables allowed as operands.
1.16 Theory of Computation

Basis
Any number or letter (i.e., a variable) is an expression.
Induction
If E and F are expressions, then so are E + F, E*F, and (E).

Example:

Both 2 and x are expressions by the basis. The inductive step tells us x+2, (x + 2)
and 2*(x + 2) are all expressions. Notice how each of these expressions depends on the
previous ones being expressions.

When we have a recursive definition, we can prove theorems about it using the
following proof form, which is called structural induction.

Let S(X) be a statement about the structures X that are defined by some particular
recursive definition.

àà As a basis, prove S(X) for the basis structure(s) X.

àà For the inductive step, take a. structure X that the recursive definition says is
formed from Y 1,Y2,..., Yk. Assume that the statements S(Y1), S(Y2), ….., S(Yk),
and use these to prove S(X).

Our conclusion is that S(X) is true for all X. The following Theorem gives the
facts and proof for trees and expressions.

Theorem 10

Every tree has one more node than it has edges.

Proof

The formal statement S(T) we need to prove by structural induction is: “if T is a
tree, and T has n nodes and e edges, then n = e + 1”.

Basis

The basis case is when T is a single node. Then n = 1 and e = 0, so the relationship
n = e + 1 holds.
Automata Fundamentals 1.17

Induction

Let T be a tree built by the inductive step of the definition, from root node N and k
smaller trees T1 , T2 ,..., Tk . We may assume that the statements S(Ti ) hold for i = 1, 2,...,
k. That is, let Ti have ni nodes and ei edges; then ni = ei + 1.

The nodes of T are node N and all the nodes of the Ti’s. There are thus 1 + n1 + n2
+....+ nk nodes in T. The edges of T are the k edges we added explicitly in the inductive
definition step, plus the edges of the Ti’s.

Hence, T has k + el + e2 + …. + ek edges ... (1.3)

If we substitute ei + 1 for ni in the count of the number of nodes of T we find that

T has 1 + [el + 1] + [e2 + 1] + …. + [ek + 1] nodes ... (1.4)

Since there are k terms in (1.3), we can regroup (1.4) as

k + 1 + el + e2 + …. + ek ... (1.5)

This expression is exactly 1 more than the expression (1.3) that was given for the
number of edges of T. Thus, T has one more node than it has edges.

Theorem 11

Every expression has an equal number of left and right parentheses.

Proof

Formally, we prove the statement S(G) about any expression G that is defined by
the recursion example described earlier the numbers of left and right parentheses in G are
the same.

Basis

If G is defined by the basis, then G is a number or variable. These expressions

have 0 left parentheses and 0 right parentheses, so the numbers are equal.

Induction

There are three rules whereby expression G may have been constructed according
to the inductive step in the definition:
1.18 Theory of Computation

rr G = E + F

rr G = E * F

rr G = (E)

We may assume that S(E) and S(F) are true; that is, E has the same number of
left and right parentheses, say n of each, and F likewise has the same number of left and
right parentheses, say m of each. Then we can compute the numbers of left and right
parentheses in G for each of the three cases, as follows:

1. If G = E + F

Then G has n + m left parentheses and n + m right parentheses; n of each come

from E and m of each come from F.

2. If G = E * F

The count of parentheses for G is again n + m of each, for the same reason as in
case (i).

3. If G = (E)

Then there are n + l left parentheses in G -- one left parenthesis is explicitly

shown, and the other n are present in E. Likewise, there are n + 1 right parentheses in G;
one is explicit and the other n are in E.

In each of the three cases, we see that the numbers of left and right parentheses in
G are the same. This observation completes the inductive step and completes the proof.

1.4.3 Mutual Inductions

àà Sometimes, we cannot prove a single statement by induction, but rather need to

prove a group of statements S1(n), S2(n),...., Sk(n) together by induction on n.

àà Automata theory provides many such situations. In the following example we

sample the common situation where we need to explain what an automaton does
by proving a group of statements, one for each state.

àà These statements tell under what sequences of inputs the automaton gets into each
of the states.
Automata Fundamentals 1.19

Strictly speaking, proving a group of statements is no different from proving the

conjunction (logical AND) of all the statements. For instance, the group of statements
S1(n), S2(n),...., Sk(n) could be replaced by the single statement

S1(n) AND S2(n) AND .... AND Sk(n)

However, when there are really several independent statements to prove, it is

generally less confusing to keep the statements separate and to prove them all in their
own parts of the basis and inductive steps. This sort of proof is called mutual induction.
We will illustrate the necessary steps for a mutual recursion.

Example:

Let us take the on/off switch, which can be represented as an automaton. The
automaton itself is reproduced as given below.
Push
Start off on
Push

Since on pushing the button switches the state between on and off, and the switch
starts out in the off state, we expect that the following statements will together explain
the operation

Push of the switch

1. S1 (n)

The automaton is in state off after n pushes if and only if n is even.

2. S2 (n)

The automaton is in state on after n pushes if and only if n is odd.

We might suppose that S 1 implies S2 and vice-versa, since we know that a number
n cannot be both even and odd. However, what is not always true about an automaton is
that it is in one and only one state. It happens that the automaton is always in exactly one
state, but that fact must be proved as part of the mutual induction.

We give the basis and inductive parts of the proofs of statements S1(n) and S2(n)
below. The proofs depend on several facts about odd and even integers:
1.20 Theory of Computation

* if we add or subtract 1 from an even integer.

* We get an odd integer

* If we add or subtract 1 from an odd integer we get an even integer.

Basis

For the basis, we choose n = 0. Since there are two statements, each of which must
be proved in both directions (because S1 and S 2 are each “if-and-only-if” statements),
there are actually four cases to the basis, and four cases to the induction as well.

i. [S1; If]

Since 0 is in fact even, we must show that after 0 pushes, the automaton is in state
off. Since that is the start state, the automaton is indeed in state off after 0 pushes.

ii. [S1; Only-if ]

The automaton is in state off after 0 pushes, so we must show that 0 is even. But
0 is even by definition of “even”, so there is nothing more to prove.

iii. [S2; If]

The hypothesis of the “if” part of S2 is that 0 is odd. Since this hypothesis H is
false, any statement of the form “if H then C” is true, which has discussed earlier. Thus,
this part of the basis also holds.

iv. [S2; Only-if]

The hypothesis, that the automaton is in state on after 0 pushes, is also false, since
the only way to get to state on is by following an arc labeled Push, which requires that the
button be pushed at least once. Since the hypothesis is false, we can again conclude that
the if-then statement is true.

1.5 Finite Automata

Finite state automaton is an abstract model of a computer. It is represented in the
figure. The components of the automaton are: Input Tape, Finite Control and Tape Head.

Input: String
Automata Fundamentals 1.21

Finite Tape Head

State
Input Tape
Control
0 1 0 1 1

Fig. 1.1 The Working Model of a Finite Automata

Operation

String Processing (scans the string from left to right, one symbol at a time and
moves from state to state ) using its transition function.

Output: Yes/No (Accepted/Rejected)

1.5.1 Mathematical Representation

A Finite Automaton(FA) is represented by a 5-tuple machine.

M = (Q, Σ, δ, q0, F)

* Q is a finite non-empty set of states

* Σ is a finite non-empty set of symbols

* ( an alphabet)‫‏‬

* δ : QX Σ → Q is the transition function

* q0 ϵ Q is the start state

* F ϵ Q is a set of final states

1. Transition function

It is a function which guides the automata in string processing. It takes two inputs
(a state, a symbol) and gives one output (state). Transition function can be represented in
three ways. They are,
1.22 Theory of Computation

i. Diagrammatic representation
Nodes and edges are used. Nodes represent the states and edges represent the
moves. The labels of the edges represent the processing symbols. There are two types
of nodes: a) single circled node indicating non-final (non-accepting ) state; b) double
circled node indicating final state.

ii. Tabular representation

It consists of Rows and columns. Rows indicate state and columns indicate
symbol. The entries of the table indicate the output state. The arrow and star symbols are
used to point out the starting and final states respectively.

iii. Functional representation

The name of the function is δ. The input parameters are q,a.

* Where q is a state and a is a symbol. The function returns a state p.

Example:

The automata of the language L={w | w contains ab}

2. Diagrammatic Representation - Transition diagram

b a a,b

a b
q q q

Fig. 1.2 The transition diagram of FA for the language L={w | w contains ab}

δ:

Q = {q0,q1,q2}

Σ = {a,b}

q0 = q0

F = q2
Automata Fundamentals 1.23

Table 1.2 The transition table of FA for the language L={w | w contains ab}

Δ a b

→q0 q1 q0

q1 q1 q2

* q q q

3. Functional Representation - Transition functions

δ(q0 , a) = q1 δ(q0 , b) = q0

δ(q1 , a) = q1 δ(q1 , b) = q2

δ(q2 , a) = q2 δ(q2 , b) = q2

1.5.2 Types of Finite Automata

1. Deterministic

àà If there is exactly one output state in every transition function of an automata, then
the automata is called Deterministic finite Automata (DFA)

àà A Deterministic finite automaton (DFA) is represented by a 5-tuple machine

i.e. M = (Q, Σ, δ, q0, F)

* Q is a finite non-empty set of states

* Σ is a finite non-empty set of symbols

* ( an alphabet)‫‏‬

* δ : QX Σ → Q is the transition function

* q0 ϵ Q is the start state

* F ϵ Q is a set of final states

1.24 Theory of Computation

2. Non-Deterministic

àà If there is zero or more output states in any of the transition functions of an

automata then that automata is called Non-Deterministic Finite Automata (NFA).

àà NFA is the preliminary form of a machine, which can be easily constructed using
the basic constraints of a language.

àà Then it can be converted into DFA using subset construction method and finally
minimization methods are used to reduce the size of the machine.
àà A Non-Deterministic finite automaton (NFA) is represented by 5-tuples.

i.e. M = (Q, Σ, δ, q0, F)

* Q is a finite non-empty set of states

* Σ is a finite non-empty set of symbols

( an alphabet)‫‏‬

* δ: QX Σ → 2Q (subset of Q) is the transition function

* q0 ϵ Q is the start state

* F ϵ Q is a set of final states

3. ε-NFA

àà If there is a transition for ε symbol in NFA , then the automata is called ε-NFA.
An ε-Non-Deterministic finite automaton (NFA) is represented by 5-tuples.

i.e. M = (Q, Σ, δ, q0, F)

* Q is a finite non-empty set of states

* Σ is a finite non-empty set of symbols

( an alphabet)‫‏‬

* δ : QX (Σ { ε })→ 2Q (subset of Q) is the transition function

* q0 ϵ Q is the start state

* F ϵ Q is a set of final states
Automata Fundamentals 1.25

1.5.3 Language of an Automata

1. L(M)

àà The language of machine M

àà Set of all strings machine M accepts

2. L(DFA)
{w dˆ(q0 , w ) = p ∈ F }

Where,

dˆ(q0 , w ) is an extended transition function that takes a state q0 and a string w and
returns a state p which is in F = Regular language.

3. L(NFA)

{w dˆ(q0 , w ) ∩ F ≠ j) - Regular language.

1.6 Deterministic Finite Automata(DFA)

Deterministic finite Automata is a definite model of computation where there is

single output for every symbol from every state. The transition table of a DFA will be
complete and unambiguous. There would not be any empty entry and multiple entries.

1.6.1 String Processing

àà An automata processes the given string and gives Yes/No as the output.

àà During string processing, the symbols in the given string are processed one by one,
from left to right according to the moves defined by the transition functions of the
automata.

àà A set of transition function defines an automata.

àà During string processing, automata selects the transition function whose input
matches with the current state (state and symbol) and performs a move to output
state.
1.26 Theory of Computation

1.6.2 String Processing in DFA

Problem 1.1

Let M = (Q, Σ, δ, q0, F) where Q={ q0 , q1 ,q2 }, Σ,={a,b} F={q2}

δ a b

→q0 q1 q0

q1 q1 q2

* q2 q2 q2

àà Show that the string w= bbabb is accepted by the given FA, M.

dˆ(q0 , bbabb) = dˆ(q0 , babb)

=dˆ(q , abb)
0

=dˆ(q1 , bb)
= d (q2 , b)
= q2 ∈ F

àà There is a path from starting state to final state.

b b a b b
q0 q0 q0 q1 q2 q2 F

Therefore the given string is accepted.

Problem 1.2

Consider the following DFA. Compute dˆ(q0 ,1101)

q0 0
q1 1 q2
0 0,1
Automata Fundamentals 1.27

dˆ(q0 ,1101) = ( q2 ,101) = ( q1 , 01) = (q0 ,1) = q2 ∈ F

So the string is not accepted.

1.7 Non-Deterministic Finite Automata(NFA)

NFA is the simple and initial model of computation .Constructing Automata to
recognize a Language includes the following steps:

rr Design an NFA

rr Convert NFA to DFA

rr Minimize the DFA

1.7 .1 Designing NFA for a language

It is very easy to design NFA for a language by considering the common

(compulsory) part of the strings in a given language. There are two types of NFAs.

rr NFA without ε-Transitions

rr ε-NFA

àà Designing NFA without ε-Transitions for a language

Problem 1.3

Design an NFA for the following finite languages over the alphabet {a,b}

a. L={ε}

b. L={a}

c. L={b}

d. L={a,b}

e. L={aa,ab}

f. L={aba,abb,aaa}
1.28 Theory of Computation

Solutions:
a. L={ε}

NFA M=(Q, Σ, δ, q0, {q0})

Where Q={ q0}

Σ={a,b}

δ : Transition diagram

q0

b. L={a}

NFA M=(Q, Σ, δ, q0, {q1})

Where Q={ q0, q1}

Σ={a,b}

δ : Transition diagram

a
q0 q
1

c. L={b}

NFA M=(Q, Σ, δ, q0, {q1})

Where Q={ q0, q1}

Σ={a,b}

δ : Transition diagram

b
q0 q1
0
Automata Fundamentals 1.29

d. L={a,b}

NFA M=(Q, Σ, δ, q0, {q1, q2})

Where Q={ q0, q1, q2}

Σ={a,b}

δ : Transition diagram

a
q0 q1
0
b
0
1
q
2

e. L={aa,ab}

NFA M=(Q, Σ, δ, q0, {q2, q3})

Where Q={ q0, q1, q2, q3}

Σ={a,b}

δ : Transition diagram

a a
q0 q q2
1

0 1 b
2

q
3

f. L={aba,abb,aaa}

NFA M=(Q, Σ, δ, q0, {q3, q5, q6})

Where Q={ q0, q1, q2, q3, q4, q5, q6}

Σ={a,b}
1.30 Theory of Computation

δ : Transition diagram

a a a
q0 q1 q2 q3
b
q4 b
q5
a
q6

Problem 1.4

Design an NFA without ε-Transitions for the following infinite languages over the
alphabet {a,b}.

a. The set of all strings ending in aa (L={w| w ends in aa})

b. The set of all strings with the substring aba(L={w| w has substring aba}).

c. The set of all strings beginning with bb (L={w| w begins with bb)}).

d. The set of all strings with even number of a’s (L={w| w has even number
of a’s}).

e. The set of all strings with even number of b’s(L={w| w has even number
of b’s }).

f. The set of all strings with odd number of a’s (L={w| w has odd number of
a’s}).

g. The set of all strings with odd number of b’s (L={w| w has odd number of
b’s}).

h. The set of all strings whose third symbol from the right end is b (L={w| w’s
third symbol from the right end is b}).

i. The set of all strings whose third symbol from the left end is b (L={w| w’s
third symbol from the left end is b}).
Automata Fundamentals 1.31

Solutions:
a. The set of all strings ending in aa.

NFA M=(Q, Σ, δ, q0, {q2})

Where Q={ q0, q1, q2}

Σ={a,b}

δ : Transition diagram

a,b
a a
q0 q q2
1

0 1

b. The set of all strings with the substring aba.

NFA M = (Q, Σ, δ, q0, {q3})

Where Q={ q0, q1, q2, q3}

Σ={a,b}

δ : Transition diagram

a,b

c. The set of all strings beginning with bb.

NFA M=(Q, Σ, δ, q0, {q2})

Where Q={ q0, q1, q2}

Σ={a,b}
1.32 Theory of Computation

δ : Transition diagram
a,b
b b
q0 q q
1 2
0 1
d. The set of all strings with even number of a’s.

NFA M=(Q, Σ, δ, q0, {q0})

Where Q={ q0, q1}

Σ={a,b}

δ : Transition diagram

b a b
q q
0 1
0 a 1

e. The set of all strings with even number of b’s.

NFA M=(Q, Σ, δ, q0, {q0})

Where Q={ q0, q1}

Σ={a,b}

δ : Transition diagram

a b a
q0 q
1

0 b 1

f. The set of all strings with odd number of a’s.

NFA M=(Q, Σ, δ, q0, {q1})

Where Q={ q0, q1}

Σ={a,b}
Automata Fundamentals 1.33

δ : Transition diagram

b b
a
q q
0 1

0 a 1

g. The set of all strings with odd number of b’s.

NFA M=(Q, Σ, δ, q0, {q1})

Where Q={ q0, q1}

Σ={a,b}

δ : Transition diagram

a a
b
q q
0 1
0 b 1

h. The set of all strings whose third symbol from the right end is b.

NFA M=(Q, Σ, δ, q0, {q3})

Where Q={ q0, q1 q2, q3}

Σ={a,b}

δ : Transition diagram

a,b
b a,b a,b
q0 q1 q2 q3

i. The set of all strings whose third symbol from the left end is b.

NFA M=(Q, Σ, δ, q0, {q3})

Where Q={ q0, q1 , q2, q3 }

Σ={a,b}
1.34 Theory of Computation

δ : Transition diagram
a,b
a,b a,b b
q0 q1 q2 q3

1. Automata for L

If the automata is given for a language Ḹ , then the automata for can be easily
constructed by changing all the non-final states to final states and final states to non-final
states.
Given:
The FA of L= {w | w consists of 10 as substring}

M(L) =(Q, Σ, δ, A, {C})

Where Q={ A, B ,C }

Σ={a,b}

δ : Transition diagram
1 0,1
0

A B C
1 0
0 0
M( L ) = (Q, Σ, δ, A, {A, B})

Where Q={ A, B ,C }

Σ={a,b}

δ : Transition diagram

0 1 0,1

A C
A B
1 0
0
Automata Fundamentals 1.35

2. Automata for L1  L 2

The intersection of two regular languages can be constructed by taking Cartesian

product of states.

Let, M (L1) = (Q1, Σ, δ1, q1, F1)

M (L2) = (Q2, Σ, δ2, q2, F2)

Then M ( L1 ∩ L2 ) = (Q2 X Q2, Σ, δ, (q1 ,q2), F2 X F2)

Problem 1.5

Let L1 = The set of all strings with even number of b’s.

NFA M(L1 ) = (Q, Σ, δ1, p, {p})

Where Q={p, q }

Σ={a,b}

δ1 : Transition diagram

a b a
p q
b

Problem 1.6

Let L2 = The set of all strings with odd number of a’s.

NFA M(L2) = (Q, Σ, δ2, r, {s})

Where Q={ r, s }

Σ={a,b}
1.36 Theory of Computation

δ2 : Transition diagram

b b
a
r s
a
Then, M(L1 ∩ L2) = ({pr, ps, qr,qs}, {a,b}, δ, pr, ps)

d ( pr , a) = ( d1 ( p, a), d2 (r , a))
= ( p, s )
d ( pr , b) = ( d1 ( p, b), d2 (r , b))
= ( q, r )

a
pr ps
a
b b b b
a
qr qs
a

1.7.2 String Processing in NFA

Problem 1.7

For the NFA M given in the following table, test whether the strings 01122, 1221
are accepted by M.

δ 0 1 2
→*q0 {q0, q1, q2 } {q1, q2 } {q2 }

*q1 Ф {q1, q2 } {q2 }

*q2 Ф Ф {q2 }
Automata Fundamentals 1.37

i. d (q0 , 01122) = dˆ({q0 , q1 , q2 },1122)

= dˆ({d (q0 ,1) ∪ d (q1 ,1) ∪ d (q2 ,1)},122)
= dˆ({q , q },122)
1 2

= dˆ({q1 , q2 }, 22)
= dˆ({q }, 2)
2

= q2 ∈ F

There is at least one path from the starting state to final state. Therefore the given
string is accepted.

0 1 1 2 2
q0 q0 q1 q1 q2 q2 ∈ F
0 q1 1
q2 1 q2
0
q2

ii. dˆ(q0 ,1221) = dˆ({q1 , q2 }, 221)

= dˆ({d (q1 , 2) ∪ d (q2 , 2)}, 21)
= dˆ({q }, 21)
2

= dˆ({q2 },1)
=f ∉ F

1 q 2 q2 2 q2 1
q0 1 f∉F
q2 2 q 2 q2 1 f ∉ F
2

There is no even a single path from starting state to final state. Therefore the given
string is not accepted.
1.38 Theory of Computation

1.7.3 Equivalence of NFA and DFA (Converting NFA to DFA)

Theorem 12

A Language L is accepted by some DFA if and only if L is accepted by some

NFA.

Proof by induction

The “if” part : If L is accepted by some NFA then L is accepted by some DFA. If
D={QD , Σ, δD, {q0},FD} is the DFA constructed from NFA, N={QN , Σ, δN, q0,FN} by the
subset construction ,then L(D) = L(N).

Proof

To prove by induction on w dˆD ({q0 }, w ) = dˆN (q0 , w ) ... (1.6)

Observe that each of the d̂ functions returns a set of states from QN, but dˆD
interprets this set as one of the states of QD (which is the power set of QN ), while interprets
this set as a subset of QN.

Basis

Let w = 0 ; that is, w=e. By the basis definitions of d̂ for DFA’s and NFA’s, both
dˆD ({q0 }, e ) and dˆN (q0 , e ) are {q 0 }
Induction

Let w = n + 1 , and assume the statement for length n. Break w as w=xa, where
a is the final symbol of w.

By the inductive hypothesis,

dˆD ({q0 }, x ) = dˆN (q0 , x )

Let both these sets of N’s states be {P1, P2,...... Pk} .i.e.

dˆD ({q0 }, x ) = dˆN (q0 , x ) = { p1 , p2 ,.... pk } ... (1.7)

The inductive part of the definition of for the NFA’s say that
Automata Fundamentals 1.39

k
ˆ
dN (q0 , w ) = i=1 dN ( pi , a) ... (1.8)

The subset construction, on the other hand , says that

k

dD ({ p1 , p2 ,.... pk } , a) = i=1 dN ( pi , a) ... (1.9)

From (1.7) and (1.9), the inductive part of the definition of d̂ for DFA is written as:

dˆD ({q0 }, w ) = dD ( dˆD ({q0 }, x ), a)

k
= dD ({ p1 , p2 ,.... pk } , a) =  dN ( pi , a) ... (1.10)
i =1

Thus, equations (1.8) and (1.10) demonstrate that

ˆ ˆ
dD ({q0 }, w ) = dN (q0 , w )

When we observe that D and N both accept w if and only if dˆD ({q0 }, w ) or
dˆN (q0 , w ) respectively, contain a state in FN.

Hence, L(D) = L(N) is proved.

The “only if” part
If L is accepted by some DFA then L is accepted by some NFA.

We have only to convert a DFA into identical NFA.Put intuitively, if we have the
transition diagram for a DFA, we can also Interpret it as the transition diagram of an NFA,
which happens to have exactly one choice of transition in any situation.

More formally, let D={Q, Σ, δD, q0,F} be a DFA. Define N={Q, Σ, δN, q0,F} to be
the equivalent NFA.

Where, dN is defined by the rule:

If dD (q, a) = p then dN (q, a) = { p}

It is then easy to show by induction on w , that if dˆD (q0 , w ) = p then dˆN (q0 , w ) = { p}

As a consequence, ω is accepted by D if and only if it is accepted by N; i.e .,

L(D)=L(N).
1.40 Theory of Computation

Subset construction method (with ‘Lazy Evaluation’) is used to convert NFA to

DFA. In this method the transition functions are generated only for reachable states.

Method 1

Steps

1. Include the starting state of NFA (q0) in DFA as starting state of DFA.

2. Find the transition for all the symbols from q0

3. If the output state is new state, include it in DFA and find the transition for
all the symbols from that state.

4. Repeat step3 until there are no more new states.

5. The state which includes final state of NFA is the final state of DFA.

Problem 1.8

Construct the DFA for the L={w|w ends in 01}

Transition Diagram of NFA

0,1
0 1
q0 q q
1 2
0 1

Transition Table of NFA

δD 0 1 2

→q0 {q0, q1 } {q0} {q2 }

{q0, q1 } {q0, q1 } { q0,q2} {q2}

* { q0,q2} {q0, q1} {q0} {q2}

Automata Fundamentals 1.41

Step 1:
Include q0

Step 2:
Find transitions for 0,1 from q0.

d ( q0 , 0) = {q0 , q1} - New state

d ( q0 ,1) = {q0 } - Existing state

Step 3:
Find transitions for 0,1 from new state.

d ({q0 , q1}, 0) = d (q0 , 0) ∪ d (q1 , 0)

= {q0 , q1} ∪ j = {q0 , q1} Existing state
d ({q0 , q1},1) = d (q0 ,1) ∪ d (q1 ,1)
= {q0 } ∪ {q2 } = {q0 , q2 } New state

Step 4:

Repeat step 3 for new state (s).

d ({q0 , q2 }, 0) = d (q0 , 0) ∪ d (q2 , 0)

= {q0 , q1} ∪ j = {q0 , q1} Existing state
d ({q0 , q2 },1) = d (q0 ,1) ∪ d (q2 ,1)
= {q0 } ∪ j} = {q0 } New state

Transition Diagram of DFA

1 0

q0 0 {q0, q1} 1 {q0, q2}

1 0
1.42 Theory of Computation

Method 2

Input: Transition table of NFA

Output: Transition table of DFA

Steps

1. Draw the transition table for NFA (if not given)

2. Copy the first row of NFA table (transition function of start state) to DFA
table.

3. The entries are considered as states of DFA.

4. If there is any new state, find the transition function for that new state using
the following formula:
k
dD ({q1 ,..., qk }, a) =  dN (qi , a)
i =1

5. Continue Step 4 until no more new states.

Transition Table of DFA

δD 0 1

→q0 {q0, q1} {q0}

{q0, q1} {q0, q1} { q0,q2}

* { q0,q2} {q0, q1} {q0}

Procedure

^^ Copy the first row. {q0, q1}is the new state.

^^ Union of q0 row and q1 row. {q0, q2 }is the new state.

^^ Union of q0 row and q2 row.

^^ No more new states. So Stop

Automata Fundamentals 1.43

Transition Diagram of DFA

1 0

q0 0 {q0, q1} 1 {q0, q2}

1 0

Q = {q0, { q0,q1} ,{q0,q2}}

Σ = {0,1}

q0 = q0

F ={q0,q2}

Problem 1.9

Consider the following NFA. Convert it into DFA.

Transition Table of NFA

δN a b

→q0 { q0,q1} {q0}

q1 q2 q1

q2 q3 q3

* q3 - q2

Procedure

^^ Copy the first row.

^^ Identify the new state.

^^ Find the transition for new state using Union operation.

^^ Stop, if no more new states.

1.44 Theory of Computation

Transition Diagram of DFA

a,b

b b
a a {q0, q1,q2} b {q0, q1,q3}
q0 {q0, q1 }

a,b
{q0,q1,q2,q3}

Problem 1.10

Convert to the DFA the following NFA.

δN 0 1

→p { p,r } {q}

q { r,s } { p}

*r { p,s} {r}

*s { q,r } -

Transition Table of DFA

δD 0 1

→p { p,r } { q}

{ q} { r,s } { p}
Automata Fundamentals 1.45

*{ p,r } { p,r,s } { q,r }

*{ r,s } { p,q,r,s } { r}

*{ p,r,s } { p,q,r,s } { q,r }

*{ r} { p,s} {r}

*{ p,q,r,s } { p,q,r,s } { p,q,r }

*{ p,s} { p,q,r } { q}

*{ p,q,r } { p,r,s } { p,q,r }

*{ q,r } { p,r,s } { p,r }

Transition Diagram of DFA

0 1
{p,r} {q,r }
p
1
1 1 1
1
0 0
q {r,s} {p,r,s} 0 {p,q,r}

1 0
1 0 1
{p,s}
0
{r} {p,q,r.s} 1

1
0 0
1.46 Theory of Computation

Problem 1.11
Convert the following NFA to a DFA and informally describe the language it
accepts.
Transition table of given NFA

δN 0 1

→p { p,q } { p}

q { r,s } { t}

r { p,r} {t}

*s - -

*t - -

Transition table of DFA

δD 0 1

→p { p,q } { p}

{ p,q} {p,q, r,s } { p,t}

*{ p,q,r,s } { p,q,r,s } { p,t }

*{p,t} { p,q } { p}

Transition Diagram of DFA

1
0
0 {p,q} 0
{p} {p,q,r,s}}
0 1
0 1
{p,t}
Automata Fundamentals 1.47

Problem 1.12

Convert to a DFA the following NFA.

0 1

→p {q,s} {q}

*q {r} {q,r}

r {s} {p}

*s - {p}

Transition Diagram of DFA

1
{p} 0
{q,s}
{q,r}
1

1 0
1 1 1
1
{r}
{s}
0 {p,q,r}

0 0
0
1
{r,s}
[q, {q,r,s}
s] 0

Language of DFA

àà The language of a DFA is defined by,

L(DFA)={w dˆ(q0 , w) is in F}
1.48 Theory of Computation

àà And the language of a NFA is defined by,

L( NFA) = {w | dˆ(q0 , w) ∩ F ≠ j}

* Where q0 is the start state

* F is the set of final states and

* w is a string.

* L(DFA) and L(NFA) are called Regular Languages.

1.8 Finite Automata with Epsilon Transitions

Finite Automata with Epsilon transitions is also called as ε-NFA . It contains
epsilon edges. In transition table a column is allocated for epsilon and it gives the output
for epsilon input.

++ A Non-Deterministic finite automaton with ε- Transitions (NFA) is represented

by 5-tuples.

i.e. M = (Q, Σ, δ, q0, F)

* Q is a finite non-empty set of states.

* Σ is a finite non-empty set of symbols (an alphabet)

* δ : QX Σ U {ε} → 2Q is the transition function

* q0 ϵ Q is the start state

* F ϵ Q is a set of final states

Transition Table of ε-NFA
δN ε a b c

→p Ф {p} {q} {r}

q {p} {q} {r} Ф

*r {q} {r} Ф {p}

Automata Fundamentals 1.49

ε-Closure

Epsilon closure of a state is the set of all states that are reachable by following the
transition function from the given state through ε edge.

Problem 1.13

Consider the ε-NFA. Compute ε-Closure for each state.

δN ε 0 1 2

→q0 q1 q0 Ф Ф

q1 q2 Ф q1 Ф

*q2 Ф Ф Ф q2

rr ε-Closure (q0) = { q0 , q1, q2}

rr ε-Closure (q1) = { q1, q2}

rr ε-Closure (q2 ) = {q2}

1.8.1 Designing an ε-NFA or NFA with ε-Transitions

Problem 1.14

Design an ε-NFA for the language which consists of strings that has 1’s followed
by 2’s followed by 3’s.

1 2 3
e q e r
p

Q = {p,q,r}

Σ = {1,2,3}
1.50 Theory of Computation

Problem 1.15

Design an ε-NFA for the language b+.

e
p q
b

Q = {p,q}

Σ = {b}

Problem 1.16

Design an ε-NFA for the language which consists of strings with all a’s followed
by all b’s.
a b

q e
r

Q = {q,r}

Σ = {a,b}

1.8.2 String Processing in ε-NFA

Problem 1.17

For the ε-NFA M given in the following table, test whether the strings aabccand
abba are accepted by M.

δ ε a b c

→p {q} {p} Ф Ф

q {r} Ф {q} Ф

*r Ф Ф Ф {r}
Automata Fundamentals 1.51

Step 1:
Compute ε-Closure [states that can be reached by traveling along zero or more ε
arrows] for all states .

rr ε-Closure (p) = {p,q,r}  dˆ( p, e ) 

 
rr ε-Closure (q) = {q,r}  dˆ(q, e ) 
 
rr ε-Closure (r ) = {r}  dˆ(r , e ) 
 
Step2:
Start with ε-closure (p)= {p,q,r}

Where, p is the starting state of given ε –NFA.

1. (p)= {p,q,r}

dˆ({ p, q, r}, aabcc)

= dˆ(e − closure( d ( p, a ) ∪ d (q, a ) ∪ d (r , a )), abcc)
= dˆ(e − closure( p ), abcc)
= dˆ({ p, q, r}, abcc)
= dˆ(e − closure( d ( p, a ) ∪ d (q, a ) ∪ d (r , a )), bcc)
= dˆ({ p, q, r}, bcc)
= dˆ(e − closure( d ( p, b) ∪ d (q, b) ∪ d (r , b)), cc)
= dˆ({q, r}, cc)
= dˆ(e − closure( d (q, c) ∪ d (r , c)), c)
= dˆ({q, r}, c)
= r ∈F

^^ Therefore the given string is accepted.

1.52 Theory of Computation

2. w=abba

dˆ({ p, q, r}, abba )

= dˆ(e − closure( d ( p, a ) ∪ d (q, a ) ∪ d (r , a )), bba )
= dˆ(e − closure( p ), bba )
= dˆ({ p, q, r}, bba )
= dˆ(e − closure( d ( p, b) ∪ d (q, b) ∪ d (r , b)), ba )
= dˆ({q, r}, ba )
= dˆ(e − closure( d (q, b) ∪ d (r , b)), a )
= dˆ({q, r}, a )
= j ∉F

^^ Therefore the given string is not accepted.

1.8.3 Equivalence of ε-NFA and DFA.

An ε-NFA can be converted into DFA. The subset construction method (with ‘Lazy
Evaluation’) is used to convert ε-NFA to DFA. In this method the transition functions are
generated only for reachable states.

Input: Transition table of ε-NFA

Output: Transition table of DFA

Theorem
A language L is accepted by some -NFA if and only if L is accepted by some
DFA.

Proof

1. If part: If the L is accepted by some DFA then L is accepted by some -NFA

Suppose L=L(D)for some DFA. Turn D into an ε-NFA by adding transitions

d (q, e ) = j for all states q of D. Technically we must also convert the transitions of D on
input symbols, example, dD (q, a ) = p , into an NFA-transition to the set containing only
p, that is, dE (q, a ) = { p}
Automata Fundamentals 1.53

Thus, the transitions of E and D are the same , but E explicitly states that there are
no transitions out of any state on ε.

2. Only -If part: If the L is accepted by some -NFA then L is accepted by some
DFA.

Let E = {QE, Σ, δE, q0, FE} be an ε -NFA. Apply the modified subset construction
to produce the DFA.

D = {QD, Σ, δD, qD, FD}

^^ We need to show that L(D) = L(E), and we do so by showing that the extended
transition functions of E and D are the same.

^^ Formally, we show dˆE (q0 , w) = dˆD (qD , w) by induction on the length of ω .

Basics
* If w then w=ε.

* We know dˆE (q0 , e ) = ECLOSURE (q0 )

* We also know that qD = ECLOSURE (q0 ) , because that is how the start state
of D is defined.

* Finally, for a DFA, we know that dˆ( p, e ) = p for any state p, so in particular
dˆD (qD , e ) = ECLOSURE (q0 ) .

* We have thus proved that dˆE (q0 , e ) = dˆD (qD , e ) .

Induction
* Suppose w=xa.

rr Where, a is the final symbol of w and assume that the statement holds
for x.

* That is, dˆE (q0 , x) = dˆD (qD , x) .

* Let both these sets of states be {p1, p2,....pk}. By the definition of d̂ for ε-
NFA’s, we compute dˆE (q0 , w) by,
1.54 Theory of Computation

i. Let {r1, r2,....rm} be  ki=1 dE ( pi , a ) .

ii. Then dˆE (q0 , w) =  mj =1 ECLOSURE (rj )

* If we examine the construction of DFA D in the modified subset construction,

we see that δD({p1, p2,....pk},a) is constructed by the same above two steps (i)
and (ii).

* Thus, dˆD (qD , w) , which is δD({p1, p2,....pk},a) is the same set as dˆE (q0 , w) .

* We have now proved that dˆE (q0 , w) = dˆD (qD , w) and completed the inductive
part.

Steps to convert ε-NFA to DFA

a. Compute the ε-Closure for each state.

b. Draw the transition table for ε-NFA (if not given)

c. Start state of DFA is ε-Closure(q0)

• Where q0 is the start state of ε-NFA .

d. Find the transition function for ε-Closure(q0).

e. The entries are considered as states of DFA.

f. If there is any new state, find the transition function for that new state using
the following formula:
k
dD ({q1 ,..., qk }, a ) =  e − closure( dN (qi , a ))
i =1

g. Continue the above step ‘f’ until no more new states.

1.8.4 Applications and Limitations of FA

1. Applications of FA
i. Text Search

a. News Analyst - Searches on-line news

Automata Fundamentals 1.55

b. Shopping robot – Searches current prices charged for an item

c. Amazon.com - Search some keywords

d. Lexical analyzer of a compiler - Identifies the token

* Verifying the working of a physical system

* Design and construction of Softwares

ii. Advantages of Finite set of states in Automata

^^ Implement a system with a fixed set of resources

^^ Implementing a system within a hardware circuit

^^ Complementing a system using software with a finite set of codes.

2. Limitations of FA

^^ Some languages are not regular – i.e. we cannot construct FA

Example:

* B = {0n1n | n ≥ 0} is NOT regular!

* L=wwR

* L=WW

* L=WCWR

* C = { w | w has equal number of 1s and 0s}

1.8.5 Complex Problems

1. Design a NFA that accepts set of all strings that begins with 00 and ends with 11.
Convert it into DFA.

Analysis

^^ Here we have two parts:

rr Begins with string1

1.56 Theory of Computation

rr Ends with string2

^^ Let string1 be considered as s1s2 and string 2 be considered as s3s4 where s1,s2,s3
and s4 are substrings.

^^ For all s2 and s3, if s2≠s3, we can easily construct the NFA.

^^ In this problem there is no such s2 and s3 where s2=s3. Therefore we can construct
the NFA in one step as follows:
0,1
0 0 1 1
A B C D E

^^ The DFA of this machine is given below:

δD 0 1
→ {A} {B} -
{B} {C} -
{C} {C} {C,D}

{C,D} {C} {C,D,E}

* {C,D,E} {C} {C,D,E}

Note: It is difficult to draw the NFA for the following languages wheres2=s3.

^^ Set of all strings that begins with 01 and ends with 11 [s2=1]

^^ Set of all strings that begins with 01 and ends with 10 [s2=1]

^^ Set of all strings that begins with 01 and ends with 01 [s2=01]

^^ Set of all strings that begins with 10 and ends with 10 [s2=10]

^^ Set of all strings that begins with 00 and ends with 00 [s2=00]

^^ Set of all strings that begins with 11 and ends with 11 [s2=00]
Automata Fundamentals 1.57

For these kinds of problems we can use the intersection property of regular
languages.

Problem 1.18

Design a DFA that accepts set of all strings that begins with 01 and ends with 11.

àà There are three steps, that are given below.

Step 1:
Design a DFA that accepts set of all strings that begins with 01

0,1
0 1
A B C

Step 2:
Design a DFA that accepts set of all strings that ends with 11.
0,1
1 1
D E F

Step 3:
Intersection between two DFAs (Lazy Evaluation-processing only reachable
nodes)
0
1
0 1 1
0
{AD} {BD} {CD} {CDE} {CDEF}
0
0
1.58 Theory of Computation

1.8.6 PROBLEMS
1. Consider the following ε-NFA. Covert it into DFA
Transition Table of ε-NFA
δN ε a b c
→p Ф {p} {q} {r}
q {p} {q} {r} Ф
*r {q} {r} Ф {p}

Step 1:
Compute ε-Closure [states that can be reached by traveling along zero or more ε
arrows] for all states.
 dˆ( p, e ) 
rr ε-Closure (p) = {p}  
rr ε-Closure (q) = {p,q}  dˆ(q, e ) 
 
rr ε-Closure (r ) = {p,q,r}  dˆ(r , e ) 
 
Step 2:
Start with ε-closure (p)= {p}
Where, p is the starting state of given ε –NFA.
Step 3:
Find the transition for{p}

dD ({ p}, a ) = e − closure( dN ( p, a ))
= e − closure( p )
= { p} New State
dD ({ p}, b) = e − closure( dN ( p, b))
= e − closure(q )
= { p, q} New State
dD ({ p}, c) = e − closure( dN ( p, c))
= e − closure(r )
= { p , q , r}
Automata Fundamentals 1.59

Step 4:
Find the transition for {p,q}
dD ({ p, q}, a ) = e − closure( dN ( p, a ) ∪ dN (q, a))
= e − closure( p, q )
= { p, q}
dD ({ p, q}, b) = e − closure( dN ( p, b) ∪ dN (q, b))
= e − closure(q, r )
= { p , q , r}
dD ({ p, q}, c) = e − closure( dN ( p, c) ∪ dN (q, c))
= e − closure(r )
= { p , q , r}
Step 5:
Find the transition for {p,q,r}
dD ({ p, q, r}, a ) = e − closure( dN ( p, a) ∪ dN (q, a) ∪ dN (r , a))
= e − closure( p, q, r )
= { p , q , r}
dD ({ p, q, r}, b) = e − closure( dN ( p, b) ∪ dN (q, b) ∪ dN (r , b))
= e − closure(q, r )
= { p , q , r}
dD ({ p, q, r}, c) = e − closure( dN ( p, c) ∪ dN (q, c) ∪ dN (r , c))
= e − closure( p, r )
= { p , q , r}
Step 6:
No more new states. Stop the process.

Transition Table of DFA

δD a b c
→{p} {p} {p,q} {p,q,r}
{p,q} {p,q} {p,q,r} {p,q,r}
*{p,q,r} {p,q,r} {p,q,r} {p,q,r}
1.60 Theory of Computation

Transition Diagram of DFA

a a a,b,c

{p} b {p,q} b,c {p,q,r}

c
2. Consider the following ε-NFA. Covert it into DFA

δ ε a b c
→p {q,r} Ф {q} {r}
q Ф {p} {r} {p,q}
*r Ф Ф Ф Ф

Step 1:
Compute ε-Closure [states that can be reached by traveling along zero or more ε
arrows] for all states .
 dˆ( p, e ) 
rr ε-Closure (p) = {p,q,r}  
rr ε-Closure (q) = {q}  dˆ(q, e ) 
 
rr ε-Closure (r ) = {r}  dˆ(r , e ) 
 

Step 2:
Start with ε-closure (p)= {p,q,r}

Where, p is the starting state of given ε - NFA

Step 3:
Find the transition for {p,q,r}

dD ({ p, q, r}, a) = e − closure ( dN ( p, a) ∪ dN (q, a) ∪ dN (r , a))

= e − closure ( p )
= { p , q, r }
Automata Fundamentals 1.61

dD ({ p, q, r}, b) = e − closure ( dN ( p, b) ∪ dN (q, b) ∪ dN (r , b))

= e − closure (q, r )
= {q, r} New State
dD ({ p, q, r}, c) = e − closure ( dN ( p, c) ∪ dN (q, c) ∪ dN (r , c))
= e − closure ( p, q, r )
= { p, q, r}

Step 4:
Find the transition for {q,r}

dD ({q, r}, a) = e − closure ( dN (q, a) ∪ dN (r , a))

= e − closure ( p )
= { p , q, r }
dD ({q, r}, b) = e − closure ( dN (q, b) ∪ dN (r , b))
= e − closure (r )
= {r} New State
dD ({q, r}, c) = e − closure ( dN (q, c) ∪ dN (r , c))
= e − closure ( p, q)
= { p, q, r}

Step 5:
Find the transition for {r}

dD ({r}, a) = e − closure ( dN (r , a))

= e − closure (j)
=j Dead State
dD ({r}, b) = e − closure ( dN (r , b))
= e − closure (j)
=j
dD ({r}, c) = e − closure ( dN (r , c))
= e − closure (j)
=j
1.62 Theory of Computation

Step 6:
No more new states. Stop the process.

Transition Table of DFA

δD a b c

→*{p,q,r} {p,q,r} {q,r} {p,q,r}

*{q,r} {p,q,r} {r} {p,q,r}

*{r} Ф Ф Ф

Transition Diagram of DFA

a,c

{p,q,r} b {q,r} b {r}

a,c
Ф

3. Consider the following ε-NFA. Covert a,b,c it into DFA.

Transition Table of ε-NFA

δN ε 0 1 2
→ q0 q1 q0 Ф Ф
q1 q2 Ф q1 Ф
*q2 Ф Ф Ф q2

Step 1:
Compute ε-Closure [states that can be reached by traveling along zero or more ε
arrows] for all states .

rr ε-Closure (q0) = { q0, q1, q2}  dˆ(q0 , e ) 

 
Automata Fundamentals 1.63

rr ε-Closure (q1) = { q1 ,q2}  dˆ(q1 , e ) 

 

rr ε-Closure (q2 ) = { q2}  dˆ(q2 , e ) 

 
Step 2:
Start with ε-closure (q0)= { q0, q1, q2}

Where, q0 is the starting state of given ε –NFA.

Step 3:
Find the transition for { q0, q1, q2}

dD ({q0 , q1 , q2 }, 0) = e − closure ( dN (q0 , 0) ∪ dN (q1 , 0) ∪ dN (q2 , 0))

= e − closure (q0 )
= {q0 , q1 , q2 }
dD ({q0 , q1 , q2 },1) = e − closure ( dN (q0 ,1) ∪ dN (q1 ,1) ∪ dN (q2 ,1))
= e − closure (q1 )
= {q1 , q2 } New State
dD ({q0 , q1 , q2 }, 2) = e − closure ( dN (q0 , 2) ∪ dN (q1 , 2) ∪ dN (q2 , 2))
= e − closure (q2 )
= {q2 } New State

Step 4:
Find the transition for {q1,q2}

dD ({q1 , q2 }, 0) = e − closure ( dN (q1 , 0) ∪ dN (q2 , 0))

= e − closure (j)
=j Dead State
dD ({q1 , q2 },1) = e − closure ( dN (q1 ,1) ∪ dN (q2 ,1))
= e − closure (q1 )
= {q1 , q2 }
dD ({q, r}, 2) = e − closure ( dN (q1 , 2) ∪ dN (q2 , 2))
= e − closure (q2 )
= {q2 }
1.64 Theory of Computation

Step 5:
Find the transition for {q2}

dD ({q2 }, 0) = e − closure ( dN (q2 , 0))

= e − closure (j)
=j Dead State
dD ({q2 },1) = e − closure ( dN (q2 ,1))
= e − closure (j)
=j Dead State
dD ({q2 }, 2) = e − closure ( dN (q2 , 2))
= e − closure (q2 )
= {q2 }

Step 6:
No more new states. Stop the process.

Transition Table of DFA

δD 0 1 2

→*{ q0, q1, q2} { q0, q1, q2} { q1, q2} {q2}

*{ q1, q2} Ф { q1, q2} {q2}

*{q2} Ф Ф {q2}

Transition Diagram of DFA

2
0 1 2

q0,q1,q2} 1 {q1,q2} 2 {q2}

{q0,q1,q2}
0,1
0
Ф
0,1,2
Automata Fundamentals 1.65

Q = {{q0, q1, q2},{ q1, q2},{q2} }

Σ = {0,1,2}

q0= {q0, q1, q2}

F = {{q0, q1, q2},{ q1, q2},{q2}}

4. Consider the following ε-NFA. Covert it into DFA

δN ε a b
→p {r} {q} {p,r}
q Ф {p} Ф
*r {p,q} {r} {p}

Step 1:
Compute ε-Closure [states that can be reached by traveling along zero or more ε
arrows] for all states.
 dˆ( p, e ) 
rr ε-Closure (p) = {p,q,r}  

rr ε-Closure (q) = {q}  dˆ(q, e ) 

 

rr ε-Closure (r ) = {p,q,r}  dˆ(r , e ) 

 
Step 2:
Start with ε-closure (p)= { p, q, r}

Where, p is the starting state of given ε –NFA

Step 3:
Find the transition for { p,q,r}
dD ({ p, q, r}, a) = e − closure ( dN ( p, a) ∪ dN (q, a) ∪ dN (r , a))
= e − closure (q ∪ p ∪ r )
= e − closure ( p, q, r )
= { p , q, r }
1.66 Theory of Computation

dD ({ p, q, r}, b) = e − closure ( dN ( p, b) ∪ dN (q, b) ∪ dN (r , b))

= e − closure ({{ p, r} ∪ j ∪ { p}})
= e − closure ({ p, r})
= { p , q, r }

Transition Table of DFA

δD a b
→*{ p,q,r} { p,q,r} { p,q,r}
Automata Fundamentals 1.67

REVIEW QUESTIONS

1. Convert the following NFAs to a DFA .

a.

a b
→p {p,q} p
q r r
r s -
*s s s
b.

δ a b
→p {q,s} {q}
* q {r } {q,r }
r {s} {p}
* s ϕ {p}
c.

δ a b
→p {p,q} {p}
q {r,s } {t}
r {p,r} {t}
* s ϕ ϕ
*t ϕ ϕ
2. Consider the following ε- NFA. Compute the ε- Closure of each state and find it’s
equivalent DFA .
a.

δ ε a b c
→p {q,r} - {q} {r}
q - {p} {r} {p,q}
*r - - - {r}
1.68 Theory of Computation

b.

δ ε a b c
→p ϕ {p} {q} {r}
q {p} {q} {r} ϕ
*r {q} {r} ϕ {p}
3. Construct a minimized DFA for the DFA given below.
a.

δ 0 1
→ A B E
B C F
*C D H
D E H
E F I
*F G B
G H B
H I C
*I A E
b.

δ 0 1
→A B A
B A C
C D B
*D D A
E D F
F G E
G F G
H G D
4. Construct (DFA ) an Automata for the following Language
a. D = { w | w has equal number of occurrences of 01 and 10}
b. D ={{ w | w begins with 10 and ends with 10}
c. D ={{ w | w begins with 01 and ends with 01}
Automata Fundamentals 1.69

d. D ={{ w | w begins with 10 and ends with 00}

D ={{ w | w begins with 10 and ends with 01}

5. Consider the following ε-NFA.

δ ε 0 1
→p {r} {q} {p,r}
q Φ {p } Φ
* r {p,q} {r} {p}
a. Compute the ε-closure of each state.
b. List all the possible strings of length 3 or less accepted by the automaton.
c. Convert the automaton to a DFA.

d. Compute dˆ(q0 , 0110) , where q0 is the start state.

6. Obtain the DFA equivalent to the following ε-NFA.

ε a b c
→p - {p} {q} {r}
q {p} {q} {r} -
*r {q} {r} - {p}
7. Let L be a language accepted by a NFA then show that there exists a DFA that
accepts L.
8. Design a NFA that accepts set of all strings that begins with bb and ends with aa.
Convert it into DFA.
9. Construct a minimized DFA for the DFA given below.

δ 0 1
→a b c
b c d
c c d
*d d d
*e e e
*f f e
1.70 Theory of Computation

10. Design a NFA that accepts empty string or string starts and ends with 0. Convert
it into DFA.
11. Define NFA. Explain its significance. Convert the given NFA to DFA. Prove that
both NFA and DFA accepts the string 0110.