UNIT-1

Introduction to Finite Automata & Regular Expression:

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

 Theory of Computation is how efficiently problems can be solved on a model of

computation, using an algorithm.
 It is mainly about what kind of things you can really compute mechanically, how fast
and how much space does it take to complete the task.
 Ex1: To design a machine that accepts all binary strings ends in 0 and reject all other
that does not ends in 0.
11011010 – Accept
 Ex2: To design a machine to accepts all valid ‘C’ codes. Machine will check the binary
equivalent of this code and from this binary equivalent it tells weather it is valid piece of
C code or invalid.
Question: Is it possible to design a machine?
Yes – The best example is Compiler.
 Ex3: To design a machine that accepts all valid ‘C’ codes and never goes into infinite.
Question: Is it possible to design a machine?
No

1.1 Basic Terminologies of Theory of Computation: Now, let’s understand the basic
terminologies, which are important and frequently used in the Theory of Computation.

 Symbol: A symbol (often also called a character) is the smallest building block, which
can be any alphabet, letter, or picture.
  Alphabets (Σ): Alphabets are a set of symbols, which are always finite.

 Powers of an alphabet (1): If Σ is an alphabet, we can express the set of all strings of a
certain length from that alphabet by using the exponential notation:
Σk
: the set of strings of length k, each of whose is in Σ .
Examples:
Σ0
: {ǫ}, regardless of what alphabet Σ is. That is ǫ is the only string of length 0
If Σ = {0, 1}, then:
1. Σ 1 = {0, 1}
2. Σ 2 = {00, 01, 10, 11}
3. Σ 3 = {000, 001, 010, 011, 100, 101, 110, 111}
Note: confusion between Σ and Σ 1:
1. Σ is an alphabet; its members 0 and 1 are symbols
2. Σ 1 is a set of strings; its members are strings (each one of length 1)

 String: A string is a finite sequence of symbols from some alphabet. The string is
denoted by w.
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 }
 00011001 is a string from the binary alphabet Σ= {0,1} and aabbcabcd is a string from
the alphabet Σ={a,b,c,d}.
If, w = 0110 y = 0aa x = aabcaa z = 111. Then,
o Special string − s (also denoted by X)
o Concatenation − wz = 0110111
o Length − |w| = 4 |s| = 0 |x| = 6
o Reversal − yR = aa0
Some special sets of strings are as follows −
 E* All strings of symbols from E
  E+ E* - {s}
For example,
 E = {0, 1}
 E* = {s, 0, 1, 00, 01, 10, 11, 000, 001,...}
 E+ = {0, 1, 00, 01, 10, 11, 000, 001,.}

It is not the case that a string over some alphabet should contain all the symbols from the
alpha-bet. 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
 Language: A language is a set of strings from some alphabet (finite or infinite). In other
words, any subset L of E* is a language in TOC.
Some special languages are as follows −
 {} The empty set/language, containing no string.
 {s} A language containing one string, the empty string.
Example: 1

 L1 = {Set of string of length 2}

= {aa, bb, ba, bb} Finite Language
Example: 2

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

= {a, aa, aaa, abb, abbb, ababb} Infinite Language

 Concatenation: Define the binary operation . called concatenation on Σ∗ as follows:

If a1a2a3 . . . an and b1b2 . . . bm are in Σ∗,
then a1a2a3 . . . an.b1b2 . . . bm = a1a2a3 . . . anb1b2 . . . bm

Thus, strings can be concatenated yielding another string:

If x are y be strings then x.y denotes the concatenation of x and y, that is, the string
formed by making a copy of x and following it by a copy of y.
Example 1: Let L1 be the language of all possible strings obtained by
L1 = {z, zz, zzz, zzzz . . . . . .}
This can also be written as
L1 = {zn} for n = 1, 2, 3, …..

A string of length zero is said to be null string and is represented by. Above given language L1
does not include the null string. We could have defined it so as to include . Thus, L = {zn n=0, 1,
2, 3…} contains the null string. In this language, as in any other, we can define the operation of
concatenation, in which two strings are written down side by side to form a new longer string.
Suppose u = ab and v = baa, then uv is called concatenation of two strings u and v and is uv =
abbaa and vu = baaab. The words in this language clearly analogous to the positive integers, and
the operation of concatenation are analogous to addition: zn concatenated with zm is the word
zn+m.

Example 2: If the word zzz is called c and the word zz is called d, then the word formed by
concatenating c and d is cd = zzzzz When two words in our language L1 are concatenated they
produce another word in the language L1. However, this may not be true in all languages.

 Kleene Closure Definition: Suppose an alphabet, and define a language in which any
string of letters from is a word, even the null string. We shall call this language the
closure of the alphabet. we denote it by writing * after the name of the alphabet as a
superscript, which is written as *. This notation is sometimes also known as Kleene Star.

 For a given alphabet , the language L consists of all possible strings, including the null string.
For example, If = {z}, then, * = L1 = { , z, zz, zzz …..}

Example: If = {0, 1}, then, * = { , 0, 1, 00, 01, 10, 11, 000, 001 …..}
So, we can say that Kleene Star is an operation that makes an infinite language of strings of
letters out of an alphabet, if the alphabet, However, by the definition alphabet may also be. In
that case, * is finite. By “infinite language, we mean a language with infinitely many words.

Note: Σ* is a set of all possible strings(often power set(need not be unique here or we can say
multiset) of string) So this implies that language is a subset of Σ*.This is also called a “Kleene
Star”.
Kleene Star is also called a “Kleene Operator” or “Kleene Closure”. Engineers and IT
professionals make use of Kleene Star to achieve all set of strings which is to be included from a
given set of characters or symbols. It is one kind of Unary operator. In Kleene Star methodology
all individual elements of a given string must be present but additional elements or combinations
of these alphabets can be included to any extent.

Example:
Input String: "GFG".
Σ* =
{ ε,"GFG","GGFG","GGFG","GFGGGGGGGG","GGGGGGGGFFFFFFFFFGGGGGGGG",...}
(Kleene Star is an infinite set but if we provide any grammar rules then it can work as a finite set.
Please note that we can include ε string also in given Kleene star representation.)

 Set operations on languages: Since languages are set of strings we can apply set
operations to languages. There are three operations which are performed on languages
namely: union, concatenation and kleen closure.

Let A and B be two languages over a similar alphabet:

1. The union of A and B is defined as:
A ∪ B = {w : w ∈ A or w ∈ B}
2. The concatenation of the two is defined as:
AB = {ww′ : w ∈ A and w′ ∈ B} where AB is the set of all strings obtained by taking an
arbitrary string w in A and an arbitrary string w′ in B then putting them together such that the
former is to the left of the latter.
3. The kleen closure of A is defined as:
A* = {u1u2 ... uk : k ≥ 0 and ui ∈ A for all i = 1, 2, ..., k}
Where A* is obtained by taking an infinite number of strings in A and putting them together.
Note that k cannot be zero, in this case it will correspond to an empty string ϵ and therefore ϵ ∈
A*.
An Example:
Let A = {0, 01} and B = {1, 10}.
Union: A ∪ B= {0, 01, 1, 10}
concatenation: AB = {01, 010, 011, 0110}
kleen closure: A* = {ϵ, 0, 01, 00, 001, 010, 0101, 000, 0001, 00101, ...}
1.2 Chomsky Hierarchy: As you have seen earlier, there may be many kinds of production
rules. So, on the basis of production rules we can classify a grammar.
Grammar: A context-free grammar (CFG) consisting of a finite set of grammar rules is a
quadruple
G= (N, T, P, S)
Where,
– N is a set of non-terminal symbols (N is also represented as V- the set of variables).
– T is a set of terminals where N ∩ T = NULL.
– P is a set of rules, P: N → (N ∪ T)*, i.e., the left-hand side of the production rules P does have
any right context or left context.
– S is the start symbol.
Terminals:
– Defines the basic symbols from which a string in a language is composed.
– Represented in lower case letters.
Non Terminals:
– They are special symbols that are described recursively in terms of each other and terminals,
represented in upper case letters.
Production rules:
– It defines the way in which NTs may be built from one another and from terminal.
Start Symbol:
– It is a special NT from which all the other strings are derived. It is always present in the first
rule on the LHS.
According to Chomsky classification, grammar is classified into the following types:
 1. Type 0 is known as unrestricted grammar.
2. Type 1 is known as context-sensitive grammar.
3. Type 2 is known as a context-free grammar.
4. Type 3 Regular Grammar

1. Type 0: This grammar is also called unrestricted grammar. As its name suggests, it is the
grammar whose production rules are unrestricted. All grammars are of type 0. Type-0 grammars
include all formal grammar. Type 0 grammar languages are recognized by turing machine. These
languages are also known as the Recursively Enumerable languages.

Grammar Production in the form of α→β where

\alpha is (V + T)* V (V + T)*
V: Variables
T: Terminals.
Β is (V + T)*.
In type 0 there must be at least one variable on the Left side of production.
For example:
Sab --> ba
A --> S
Here, Variables are S, A, and Terminals a, b.
2. Type 1: This grammar is also called context sensitive grammar. Type-1 grammars generate
context-sensitive languages. The language generated by the grammar is recognized by the Linear
Bound Automata .
In Type 1
 First of all Type 1 grammar should be Type 0.
 Grammar Production in the form of
α→β
|\alpha |<=|\beta |
That is the count of symbol in α is less than or equal to β
Also β € (V + T) +
i.e. β cannot be ε

For Example:
S --> AB
AB --> abc
B --> b

3. Type 2: Context-Free Grammar: Type-2 grammars generate context-free languages. The

language generated by the grammar is recognized by a Push down automata.
In Type 2:
 First of all, it should be Type 1.
 The left-hand side of production can have only one variable and there is no restriction on β.
|\alpha | = 1.
For example:
S --> AB
A --> a
B --> b
4. Type 3: Regular Grammar: Type-3 grammars generate regular languages. These languages
are exactly all languages that can be accepted by a finite-state automaton. Type 3 is the most
restricted form of grammar.
Type 3 should be in the given form only :
V --> VT / T (left-regular grammar)
(or)
V --> TV /T (right-regular grammar)
For example:
S --> a
The above form is called strictly regular grammar.
There is another form of regular grammar called extended regular grammar. In this form:
V --> VT* / T*. (Extended left-regular grammar)
(or)
V --> T*V /T* (extended right-regular grammar)
For example :
S --> ab.
1.3 Introduction of Finite Automata: Finite Automata (FA) is the simplest machine to
recognize patterns. The finite automata or finite state machine is an abstract machine that has
five elements or tuples. It has a set of states and rules for moving from one state to another but it
depends upon the applied input symbol. Basically, it is an abstract model of a digital computer.
The following figure shows some essential features of general automation.

The above figure shows the following features of automata:

1. Input
2. Output
3. States of automata
4. State relation
5. Output relation

Types of Automata: There are two types of finite automata:

1. DFA(deterministic finite automata)

2. NFA(non-deterministic finite automata)
1.3.1 DFA (Deterministic Finite Automata)-

DFA refers to deterministic finite automata. Deterministic refers to the uniqueness of the
computation. In the DFA, the machine goes to one state only for a particular input character.
DFA does not accept the null move.

A Deterministic Finite Automata consists of the following:

Q : Finite set of states.
Σ : set of Input Symbols.
q : Initial state.
F : set of Final States.
δ : Transition Function. Defined as δ : Q X Σ --> Q.
Formal specification of machine is
{ Q, Σ, q, F, δ }

For example, below DFA with Σ = {0, 1} accepts all strings ending with 0.

Figure: DFA with Σ = {0, 1}

One important thing to note is, there can be many possible DFAs for a pattern. A DFA with a
minimum number of states is generally preferred.

Transition Diagram: A transition diagram or state transition diagram is a directed graph which
can be constructed as follows:
 There is a node for each state in Q, which is represented by the circle.
 There is a directed edge from node q to node p labeled a if δ(q, a) = p.
 In the start state, there is an arrow with no source.
 Accepting states or final states are indicating by a double circle.

Some Notations that are used in the transition diagram:

There is a description of how a DFA operates:

1. In DFA, the input to the automata can be any string. Now, put a pointer to the start state q and
read the input string w from left to right and move the pointer according to the transition
function, δ. We can read one symbol at a time. If the next symbol of string w is a and the pointer
is on state p, move the pointer to δ(p, a). When the end of the input string w is encountered, then
the pointer is on some state F.

2. The string w is said to be accepted by the DFA if r ∈ F that means the input string w is
processed successfully and the automata reached its final state. The string is said to be rejected
by DFA if r ∉ F.

Example 1: DFA with ∑ = {0, 1} accepts all strings starting with 1.

Solution:
The finite automata can be represented using a transition graph. In the above diagram, the
machine initially is in start state q0 then on receiving input 1 the machine changes its state to q1.
From q0 on receiving 0, the machine changes its state to q2, which is the dead state. From q1 on
receiving input 0, 1 the machine changes its state to q1, which is the final state. The possible
input strings that can be generated are 10, 11, 110, 101, 111....... that means all string starts with
1.

Example 2: NFA with ∑ = {0, 1} accepts all strings starting with 1.

Solution:

The NFA can be represented using a transition graph. In the above diagram, the machine initially
is in start state q0 then on receiving input 1 the machine changes its state to q1. From q1 on
receiving input 0, 1 the machine changes its state to q1. The possible input string that can be
generated is 10, 11, 110, 101, 111......, that means all string starts with 1.

Transition Table: The transition table is basically a tabular representation of the transition
function. It takes two arguments (a state and a symbol) and returns a state (the "next state").

A transition table is represented by the following things:

 Columns correspond to input symbols.
 Rows correspond to states.
 Entries correspond to the next state.
 The start state is denoted by an arrow with no source.
 The accept state is denoted by a star.

Example 1:

Solution: Transition table of given DFA is as follows:

Present State Next state for Input 0 Next State of Input 1

 →q0 q1 q2

q1 q0 q2

*q2 q2 q2

Explanation:
 In the above table, the first column indicates all the current states. Under column 0 and 1,
the next states are shown.
 The first row of the transition table can be read as, when the current state is q0, on input 0
the next state will be q1 and on input 1 the next state will be q2.
 In the second row, when the current state is q1, on input 0, the next state will be q0, and
on 1 input the next state will be q2.
 In the third row, when the current state is q2 on input 0, the next state will be q2, and on 1
input the next state will be q2.
 The arrow marked to q0 indicates that it is a start state and circle marked to q2 indicates
that it is a final state.
Example 2:

Solution: Transition table of given NFA is as follows:

Present State Next state for Input 0 Next State of Input 1

→q0 q0 q1

q1 q1, q2 q2

q2 q1 q3

*q3 q2 q2

Explanation:
  The first row of the transition table can be read as, when the current state is q0, on input 0
the next state will be q0 and on input 1 the next state will be q1.
 In the second row, when the current state is q1, on input 0 the next state will be either q1
or q2, and on 1 input the next state will be q2.
 In the third row, when the current state is q2 on input 0, the next state will be q1, and on 1
input the next state will be q3.
 In the fourth row, when the current state is q3 on input 0, the next state will be q2, and on
1 input the next state will be q2.

Examples of DFA

Example 1: Design a FA with ∑ = {0, 1} accepts those string which starts with 1 and ends with
0.
Solution: The FA will have a start state q0 from which only the edge with input 1 will go to the next
state.

In state q1, if we read 1, we will be in state q1, but if we read 0 at state q1, we will reach to state
q2 which is the final state. In state q2, if we read either 0 or 1, we will go to q2 state or q1 state
respectively. Note that if the input ends with 0, it will be in the final state.

Example 2: Design a FA with ∑ = {0, 1} accepts the only input 101.

Solution: In the given solution, we can see that only input 101 will be accepted. Hence, for input
101, there is no other path shown for other input.

Example 3: Design FA with ∑ = {0, 1} accepts even number of 0's and even number of 1's.

Solution: This FA will consider four different stages for input 0 and input 1. The stages could be:
Here q0 is a start state and the final state also. Note carefully that symmetry of 0's and 1's is
maintained. We can associate meanings to each state as:

q0: state of even number of 0's and even number of 1's.

q1: state of odd number of 0's and even number of 1's.
q2: state of odd number of 0's and odd number of 1's.
q3: state of even number of 0's and odd number of 1's.

Example 4: Design FA with ∑ = {0, 1} accepts the set of all strings with three consecutive 0's.

Solution: The strings that will be generated for this particular languages are 000, 0001, 1000,
10001, .... in which 0 always appears in a clump of 3. The transition graph is as follows:

Example 5: Design a DFA L(M) = {w | w ε {0, 1}*} and W is a string that does not contain
consecutive 1's.

Solution: When three consecutive 1's occur the DFA will be:
Here two consecutive 1's or single 1 is acceptable, hence

The stages q0, q1, q2 are the final states. The DFA will generate the strings that do not contain
consecutive 1's like 10, 110, 101,..... etc.

Example 6: Design a FA with ∑ = {0, 1} accepts the strings with an even number of 0's
followed by single 1.

Solution: The DFA can be shown by a transition diagram as:

1.3.2. NFA (Non-Deterministic finite automata):

 NFA stands for non-deterministic finite automata. It is easy to construct an NFA than
DFA for a given regular language.
 The finite automata are called NFA when there exist many paths for specific input from
the current state to the next state.
 Every NFA is not DFA, but each NFA can be translated into DFA.
 NFA is defined in the same way as DFA but with the following two exceptions, it
contains multiple next states, and it contains ε transition.

In the following image, we can see that from state q0 for input a, there are two next states
q1 and q2, similarly, from q0 for input b, the next states are q0 and q1. Thus it is not
fixed or determined that with a particular input where to go next. Hence this FA is called
non-deterministic finite automata.
 Formal definition of NFA: NFA also has five states same as DFA, but with different transition
function, as shown follows:

δ: Q x ∑ →2Q
Where,
1. Q: finite set of states
2. ∑: finite set of the input symbol
3. q0: initial state
4. F: final state
5. δ: Transition function

Graphical Representation of an NFA: An NFA can be represented by digraphs called state

diagram. In which:
1. The state is represented by vertices.
2. The arc labeled with an input character show the transitions.
3. The initial state is marked with an arrow.
4. The final state is denoted by the double circle.

Examples of NFA
Example 1: Design a NFA for the transition table as given below:
Present State 0 1

→q0 q0, q1 q0, q2

q1 q3 ε

q2 q2, q3 q3
 →q3 q3 q3

Solution: The transition diagram can be drawn by using the mapping function as given in the
table.

Here,
1. δ(q0, 0) = {q0, q1}
2. δ(q0, 1) = {q0, q2}
3. Then, δ(q1, 0) = {q3}
4. Then, δ(q2, 0) = {q2, q3}
5. δ(q2, 1) = {q3}
6. Then, δ(q3, 0) = {q3}
7. δ(q3, 1) = {q3}

Example 2: Design an NFA with ∑ = {0, 1} accepts all string ending with 01.

Solution:

Hence, NFA would be:

Example 3: Design an NFA with ∑ = {0, 1} in which double '1' is followed by double '0'.

Solution: The FA with double 1 is as follows:

It should be immediately followed by double 0. Then,

Now before double 1, there can be any string of 0 and 1. Similarly, after double 0, there can be any
string of 0 and 1.

Hence the NFA becomes:

Now considering the string 01100011

1. q0 → q1 → q2 → q3 → q4 → q4 → q4 → q4

Example 4: Design an NFA in which all the string contains a substring 1110.

Solution: The language consists of all the string containing substring 1010. The partial transition
diagram can be:

Now as 1010 could be the substring. Hence we will add the inputs 0's and 1's so that the
substring 1010 of the language can be maintained. Hence the NFA becomes:
 Transition table for the above transition diagram can be given below:

Present State 0 1

→q1 q1 q1, q2

q2 q3

q3 q4

q4 q5

*q5 q5 q5

Consider a string 111010,

1. δ(q1, 111010) = δ(q1, 1100)

2. = δ(q1, 100)
3. = δ(q2, 00)

Got stuck! As there is no path from q2 for input symbol 0. We can process string 111010 in
another way.

1. δ(q1, 111010) = δ(q2, 1100)

2. = δ(q3, 100)
3. = δ(q4, 00)
4. = δ(q5, 0)
5. = δ(q5, ε)
As state q5 is the accept state. We get the complete scanned, and we reached to the final state.

Example 5: Design an NFA with ∑ = {0, 1} accepts all string in which the third symbol from
the right end is always 0.
 Solution:

Thus we get the third symbol from the right end as '0' always. The NFA can be:

The above image is an NFA because in state q0 with input 0, we can either go to state q0 or q1.

1.4 Eliminating ε Transitions-

NFA with ε can be converted to NFA without ε, and this NFA without ε can be converted to
DFA. To do this, we will use a method, which can remove all the ε transition from given NFA.
The method will be:

where qi ∈ Q.
1. Find out all the ε transitions from each state from Q. That will be called as ε-closure {q1}

2. Then δ' transitions can be obtained. The δ' transitions mean a ε-closure on δ moves.
3. Repeat Step-2 for each input symbol and each state of given NFA.
4. Using the resultant states, the transition table for equivalent NFA without ε can be built.

Example: Convert the following NFA with ε to NFA without ε.

Solutions: We will first obtain ε-closures of q0, q1 and q2 as follows:

1. ε-closure(q0) = {q0}
2. ε-closure(q1) = {q1, q2}
3. ε-closure(q2) = {q2}
Now the δ' transition on each input symbol is obtained as:
δ'(q0, a) = ε-closure(δ(δ^(q0, ε),a))
= ε-closure(δ(ε-closure(q0),a))
= ε-closure(δ(q0, a))
= ε-closure(q1)
 = {q1, q2}
δ'(q0, b) = ε-closure(δ(δ^(q0, ε),b))
= ε-closure(δ(ε-closure(q0),b))
= ε-closure(δ(q0, b))
=Ф

Now the δ' transition on q1 is obtained as:

δ'(q1, a) = ε-closure(δ(δ^(q1, ε),a))
= ε-closure(δ(ε-closure(q1),a))

= ε-closure(δ(q1, a) ∪ δ(q2, a))

= ε-closure(δ(q1, q2), a)

= ε-closure(Ф ∪ Ф)
=Ф
δ'(q1, b) = ε-closure(δ(δ^(q1, ε),b))

= ε-closure(δ(ε-closure(q1),b))

= ε-closure(δ(q1, b) ∪ δ(q2, b))

= ε-closure(δ(q1, q2), b)

= ε-closure(Ф ∪ q2)
= {q2}

The δ' transition on q2 is obtained as:

δ'(q2, a) = ε-closure(δ(δ^(q2, ε),a))
= ε-closure(δ(ε-closure(q2),a))
= ε-closure(δ(q2, a))
= ε-closure(Ф)
=Ф
δ'(q2, b) = ε-closure(δ(δ^(q2, ε),b))
= ε-closure(δ(ε-closure(q2),b))
= ε-closure(δ(q2, b))
= ε-closure(q2)
= {q2}
Now we will summarize all the computed δ' transitions:
δ'(q0, a) = {q0, q1}
δ'(q0, b) = Ф
δ'(q1, a) = Ф
δ'(q1, b) = {q2}
δ'(q2, a) = Ф
δ'(q2, b) = {q2}
The transition table can be:
 States a b

→q0 {q1, q2} Ф

*q1 Ф {q2}

*q2 Ф {q2}

State q1 and q2 become the final state as ε-closure of q1 and q2 contain the final state q2. The
NFA can be shown by the following transition diagram:

1.5 Conversion from NFA to DFA

In this section, we will discuss the method of converting NFA to its equivalent DFA. In NFA,
when a specific input is given to the current state, the machine goes to multiple states. It can have
zero, one or more than one move on a given input symbol. On the other hand, in DFA, when a
specific input is given to the current state, the machine goes to only one state. DFA has only one
move on a given input symbol.

Let, M = (Q, ∑, δ, q0, F) is an NFA which accepts the language L(M). There should be
equivalent DFA denoted by M' = (Q', ∑', q0', δ', F') such that L(M) = L(M').

Steps for converting NFA to DFA:

Step 1: Initially Q' = ϕ

Step 2: Add q0 of NFA to Q'. Then find the transitions from this start state.
Step 3: In Q', find the possible set of states for each input symbol. If this set of states is not in Q',
then add it to Q'.
Step 4: In DFA, the final state will be all the states which contain F(final states of NFA)
Example 1: Convert the given NFA to DFA.
 Solution: For the given transition diagram we will first construct the transition table.

State 0 1

→q0 q0 q1

q1 {q1, q2} q1

*q2 q2 {q1, q2}

Now we will obtain δ' transition for state q0.

1. δ'([q0], 0) = [q0]
2. δ'([q0], 1) = [q1]

The δ' transition for state q1 is obtained as:

1. δ'([q1], 0) = [q1, q2] (new state generated)

2. δ'([q1], 1) = [q1]

The δ' transition for state q2 is obtained as:

1. δ'([q2], 0) = [q2]
2. δ'([q2], 1) = [q1, q2]

Now we will obtain δ' transition on [q1, q2].

1. δ'([q1, q2], 0) = δ(q1, 0) ∪ δ(q2, 0)

2. = {q1, q2} ∪ {q2}
3. = [q1, q2]
4. δ'([q1, q2], 1) = δ(q1, 1) ∪ δ(q2, 1)
5. = {q1} ∪ {q1, q2}
6. = {q1, q2}
7. = [q1, q2]
The state [q1, q2] is the final state as well because it contains a final state q2. The transition table
for the constructed DFA will be:

State 0 1

→[q0] [q0] [q1]

[q1] [q1, q2] [q1]

*[q2] [q2] [q1, q2]

*[q1, q2] [q1, q2] [q1, q2]

The Transition diagram will be:

The state q2 can be eliminated because q2 is an unreachable state.

Example 2: Convert the given NFA to DFA.

 Solution: For the given transition diagram we will first construct the transition table.

State 0 1

→q0 {q0, q1} {q1}

*q1 ϕ {q0, q1}

Now we will obtain δ' transition for state q0.

1. δ'([q0], 0) = {q0, q1}

2. = [q0, q1] (new state generated)
3. δ'([q0], 1) = {q1} = [q1]

The δ' transition for state q1 is obtained as:

1. δ'([q1], 0) = ϕ
2. δ'([q1], 1) = [q0, q1]

Now we will obtain δ' transition on [q0, q1].

1. δ'([q0, q1], 0) = δ(q0, 0) ∪ δ(q1, 0)

2. = {q0, q1} ∪ ϕ
3. = {q0, q1}
4. = [q0, q1]

Similarly,

1. δ'([q0, q1], 1) = δ(q0, 1) ∪ δ(q1, 1)

2. = {q1} ∪ {q0, q1}
3. = {q0, q1}
4. = [q0, q1]

As in the given NFA, q1 is a final state, then in DFA wherever, q1 exists that state becomes a
final state. Hence in the DFA, final states are [q1] and [q0, q1]. Therefore set of final states F =
{[q1], [q0, q1]}.

The transition table for the constructed DFA will be:

State 0 1
 →[q0] [q0, q1] [q1]

*[q1] ϕ [q0, q1]

*[q0, q1] [q0, q1] [q0, q1]

The Transition diagram will be:

Even we can change the name of the states of DFA.

Suppose

1. A = [q0]
2. B = [q1]
3. C = [q0, q1]

With these new names the DFA will be as follows:

 1.6. Conversion from NFA with ε to DFA

Non-deterministic finite automata(NFA) is a finite automata where for some cases when a
specific input is given to the current state, the machine goes to multiple states or more than 1
states. It can contain ε move. It can be represented as M = { Q, ∑, δ, q0, F}.

Where

1. Q: finite set of states

2. ∑: finite set of the input symbol
3. q0: initial state
4. F: final state
5. δ: Transition function

NFA with ε move: If any FA contains ε transaction or move, the finite automata is called NFA
with ε move.

ε-closure: ε-closure for a given state A means a set of states which can be reached from the state
A with only ε(null) move including the state A itself.

Steps for converting NFA with ε to DFA:

Step 1: We will take the ε-closure for the starting state of NFA as a starting state of DFA.
Step 2: Find the states for each input symbol that can be traversed from the present. That means
the union of transition value and their closures for each state of NFA present in the current state
of DFA.
Step 3: If we found a new state, take it as current state and repeat step 2.
Step 4: Repeat Step 2 and Step 3 until there is no new state present in the transition table of
DFA.
Step 5: Mark the states of DFA as a final state which contains the final state of NFA.
Example 1:

Convert the NFA with ε into its equivalent DFA.

 Solution:

Let us obtain ε-closure of each state.

1. ε-closure {q0} = {q0, q1, q2}

2. ε-closure {q1} = {q1}
3. ε-closure {q2} = {q2}
4. ε-closure {q3} = {q3}
5. ε-closure {q4} = {q4}

Now, let ε-closure {q0} = {q0, q1, q2} be state A.

Hence

δ'(A, 0) = ε-closure {δ((q0, q1, q2), 0) }

= ε-closure {δ(q0, 0) ∪ δ(q1, 0) ∪ δ(q2, 0) }
= ε-closure {q3}
= {q3} call it as state B.

δ'(A, 1) = ε-closure {δ((q0, q1, q2), 1) }

= ε-closure {δ((q0, 1) ∪ δ(q1, 1) ∪ δ(q2, 1) }
= ε-closure {q3}
= {q3} = B.

The partial DFA will be

Now,

δ'(B, 0) = ε-closure {δ(q3, 0) }

=ϕ
δ'(B, 1) = ε-closure {δ(q3, 1) }
= ε-closure {q4}
= {q4} i.e. state C

For state C:
1. δ'(C, 0) = ε-closure {δ(q4, 0) }
2. =ϕ
3. δ'(C, 1) = ε-closure {δ(q4, 1) }
4. =ϕ

The DFA will be,

Example 2: Convert the given NFA into its equivalent DFA.

Solution: Let us obtain the ε-closure of each state.

1. ε-closure(q0) = {q0, q1, q2}

2. ε-closure(q1) = {q1, q2}
3. ε-closure(q2) = {q2}

Now we will obtain δ' transition. Let ε-closure(q0) = {q0, q1, q2} call it as state A.

δ'(A, 0) = ε-closure{δ((q0, q1, q2), 0)}

= ε-closure{δ(q0, 0) ∪ δ(q1, 0) ∪ δ(q2, 0)}
= ε-closure{q0}
= {q0, q1, q2}

δ'(A, 1) = ε-closure{δ((q0, q1, q2), 1)}

= ε-closure{δ(q0, 1) ∪ δ(q1, 1) ∪ δ(q2, 1)}
= ε-closure{q1}
= {q1, q2} call it as state B
 δ'(A, 2) = ε-closure{δ((q0, q1, q2), 2)}
= ε-closure{δ(q0, 2) ∪ δ(q1, 2) ∪ δ(q2, 2)}
= ε-closure{q2}
= {q2} call it state C

Thus we have obtained

1. δ'(A, 0) = A
2. δ'(A, 1) = B
3. δ'(A, 2) = C

The partial DFA will be:

Now we will find the transitions on states B and C for each input.

Hence

δ'(B, 0) = ε-closure{δ((q1, q2), 0)}

= ε-closure{δ(q1, 0) ∪ δ(q2, 0)}
= ε-closure{ϕ}
=ϕ

δ'(B, 1) = ε-closure{δ((q1, q2), 1)}

= ε-closure{δ(q1, 1) ∪ δ(q2, 1)}
= ε-closure{q1}
= {q1, q2} i.e. state B itself

δ'(B, 2) = ε-closure{δ((q1, q2), 2)}

= ε-closure{δ(q1, 2) ∪ δ(q2, 2)}
 = ε-closure{q2}
= {q2} i.e. state C itself

Thus we have obtained

1. δ'(B, 0) = ϕ
2. δ'(B, 1) = B
3. δ'(B, 2) = C

The partial transition diagram will be

Now we will obtain transitions for C:

δ'(C, 0) = ε-closure{δ(q2, 0)}

= ε-closure{ϕ}
=ϕ

δ'(C, 1) = ε-closure{δ(q2, 1)}

= ε-closure{ϕ}
=ϕ

δ'(C, 2) = ε-closure{δ(q2, 2)}

= {q2}

Hence the DFA is

 As A = {q0, q1, q2} in which final state q2 lies hence A is final state. B = {q1, q2} in which the
state q2 lies hence B is also final state. C = {q2}, the state q2 lies hence C is also a final state.

1.7 Minimization of DFA

Minimization of DFA means reducing the number of states from given FA. Thus, we get the
FSM(finite state machine) with redundant states after minimizing the FSM.

We have to follow the various steps to minimize the DFA. These are as follows:

Step 1: Remove all the states that are unreachable from the initial state via any set of the
transition of DFA.
Step 2: Draw the transition table for all pair of states.
Step 3: Now split the transition table into two tables T1 and T2. T1 contains all final states, and
T2 contains non-final states.
Step 4: Find similar rows from T1 such that:
1. 1. δ (q, a) = p
2. 2. δ (r, a) = p

That means, find the two states which have the same value of a and b and remove one of them.

Step 5: Repeat step 3 until we find no similar rows available in the transition table T1.
Step 6: Repeat step 3 and step 4 for table T2 also.
Step 7: Now combine the reduced T1 and T2 tables. The combined transition table is the
transition table of minimized DFA.
Example:
Solution:
Step 1: In the given DFA, q2 and q4 are the unreachable states so remove them.

Step 2: Draw the transition table for the rest of the states.

State 0 1

→q0 q1 q3

q1 q0 q3

*q3 q5 q5

*q5 q5 q5

Step 3: Now divide rows of transition table into two sets as:

1. One set contains those rows, which start from non-final states:

State 0 1

q0 q1 q3

q1 q0 q3

2. Another set contains those rows, which starts from final states.

State 0 1
 q3 q5 q5

q5 q5 q5

Step 4: Set 1 has no similar rows so set 1 will be the same.

Step 5: In set 2, row 1 and row 2 are similar since q3 and q5 transit to the same state on 0 and 1.
So skip q5 and then replace q5 by q3 in the rest.

State 0 1

q3 q3 q3

Step 6: Now combine set 1 and set 2 as:

State 0 1

→q0 q1 q3

q1 q0 q3

*q3 q3 q3

Now it is the transition table of minimized DFA.

1.8 Regular Expression

 The language accepted by finite automata can be easily described by simple expressions
called Regular Expressions. It is the most effective way to represent any language.
 The languages accepted by some regular expression are referred to as Regular languages.
 A regular expression can also be described as a sequence of pattern that defines a string.
  Regular expressions are used to match character combinations in strings. String searching
algorithm used this pattern to find the operations on a string.

For instance: In a regular expression, x* means zero or more occurrence of x. It can generate {e,
x, xx, xxx, xxxx, .....} In a regular expression, x+ means one or more occurrence of x. It can
generate {x, xx, xxx, xxxx, .....}

1.8.1 Operations on Regular Language: The various operations on regular language are:

Union: If L and M are two regular languages then their union L U M is also a union.

L U M = {s | s is in L or s is in M}

Intersection: If L and M are two regular languages then their intersection is also an intersection.

L ∩ M = {st | s is in L and t is in M}

Kleen closure: If L is a regular language then its Kleen closure L1* will also be a regular
language.

L* = Zero or more occurrence of language L.

Example 1: Write the regular expression for the language accepting all combinations of a's, over
the set ∑ = {a}

Solution: All combinations of a's means a may be zero, single, double and so on. If a is
appearing zero times, that means a null string. That is we expect the set of {ε, a, aa, aaa, ....}. So
we give a regular expression for this as:

R = a* That is Kleen closure of a.

Example 2: Write the regular expression for the language accepting all combinations of a's
except the null string, over the set ∑ = {a}

Solution: The regular expression has to be built for the language

L = {a, aa, aaa, ....}

This set indicates that there is no null string. So we can denote regular expression as:

R = a+

Example 3: Write the regular expression for the language accepting all the string
containing any number of a's and b's.
Solution: The regular expression will be:

R.E. = (a + b)*

This will give the set as L = {ε, a, aa, b, bb, ab, ba, aba, bab, .....}, any combination of a and b.

The (a + b)* shows any combination with a and b even a null string.

1.8.2. Examples of Regular Expression

Example 1: Write the regular expression for the language accepting all the string
which are starting with 1 and ending with 0, over ∑ = {0, 1}.

Solution: In a regular expression, the first symbol should be 1, and the last symbol should be 0.
The r.e. is as follows:

R = 1 (0+1)* 0

Example 2: Write the regular expression for the language starting and ending with a
and having any having any combination of b's in between.

The regular expression will be:

R = a b* b

Example 3: Write the regular expression for the language starting with a but not having
consecutive b's.

Solution: The regular expression has to be built for the language:

L = {a, aba, aab, aba, aaa, abab, .....}

The regular expression for the above language is:

R = {a + ab}*

Example 4: Write the regular expression for the language accepting all the string in
which any number of a's is followed by any number of b's is followed by any number
of c's.

Solution: As we know, any number of a's means a* any number of b's means b*, any number of
c's means c*. Since as given in problem statement, b's appear after a's and c's appear after b's. So
the regular expression could be:
1. R = a* b* c*

Example 5: Write the regular expression for the language over ∑ = {0} having even
length of the string.

Solution: The regular expression has to be built for the language:

1. L = {ε, 00, 0000, 000000, ......}

The regular expression for the above language is:

1. R = (00)*

Example 6: Write the regular expression for the language having a string which should
have atleast one 0 and alteast one 1.

Solution: The regular expression will be:

1. R = [(0 + 1)* 0 (0 + 1)* 1 (0 + 1)*] + [(0 + 1)* 1 (0 + 1)* 0 (0 + 1)*]

Example 7: Describe the language denoted by following regular expression

1. r.e. = (b* (aaa)* b*)*

Solution: The language can be predicted from the regular expression by finding the meaning of
it. We will first split the regular expression as:

r.e. = (any combination of b's) (aaa)* (any combination of b's)

L = {The language consists of the string in which a's appear triples, there is no restriction on the
number of b's}

Example 8: Write the regular expression for the language L over ∑ = {0, 1} such that
all the string do not contain the substring 01.

Solution: The Language is as follows:

1. L = {ε, 0, 1, 00, 11, 10, 100, .....}

The regular expression for the above language is as follows:

1. R = (1* 0*)
 Example 9: Write the regular expression for the language containing the string over {0,
1} in which there are at least two occurrences of 1's between any two occurrences of
1's between any two occurrences of 0's.

Solution: At least two 1's between two occurrences of 0's can be denoted by (0111*0)*.

Similarly, if there is no occurrence of 0's, then any number of 1's are also allowed. Hence the r.e.
for required language is:

1. R = (1 + (0111*0))*

Example 10: Write the regular expression for the language containing the string in
which every 0 is immediately followed by 11.

Solution: The regular expectation will be:

1. R = (011 + 1)*

1.9 Conversion of RE to FA- To convert the RE to FA, we are going to use a method
called the subset method. This method is used to obtain FA from the given regular expression.
This method is given below:

Step 1: Design a transition diagram for given regular expression, using NFA with ε moves.
Step 2: Convert this NFA with ε to NFA without ε.
Step 3: Convert the obtained NFA to equivalent DFA.

Example 1: Design a FA from given regular expression 10 + (0 + 11)0* 1.

Solution: First we will construct the transition diagram for a given regular expression.

Step 1:

Step 2:
Step 3:

Step 4:

Step 5:
Now we have got NFA without ε. Now we will convert it into required DFA for that, we will
first write a transition table for this NFA.

State 0 1

→q0 q3 {q1, q2}

q1 qf ϕ

q2 ϕ q3

q3 q3 qf

*qf ϕ ϕ

The equivalent DFA will be:

State 0 1

→[q0] [q3] [q1, q2]

[q1] [qf] ϕ

[q2] ϕ [q3]

[q3] [q3] [qf]

[q1, q2] [qf] [qf]

 *[qf] ϕ ϕ

Example 2: Design a NFA from given regular expression 1 (1* 01* 01*)*.

Solution: The NFA for the given regular expression is as follows:

Step 1:

Step 2:

Step 3:

Example 3: Construct the FA for regular expression 0*1 + 10.

Solution: We will first construct FA for R = 0*1 + 10 as follows:

Step 1:
Step 2:

Step 3:

Step 4:
1.10Equivalence of two Regular Expressions (Arden's Theorem)-
The Arden's Theorem is useful for checking the equivalence of two regular expressions as well
as in the conversion of DFA to a regular expression. Let us see its use in the conversion of DFA
to a regular expression. Following algorithm is used to build the regular expression form given
DFA.

1. Let q1 be the initial state.

2. There are q2, q3, q4 ....qn number of states. The final state may be some qj where j<= n.
3. Let αji represents the transition from qj to qi.
4. Calculate qi such that
qi = αji * qj
If qj is a start state then we have:
qi = αji * qj + ε
5. Similarly, compute the final state which ultimately gives the regular expression 'r'.
Example: Construct the regular expression for the given DFA

Solution: Let us write down the equations

q1 = q1 0 + ε

Since q1 is the start state, so ε will be added, and the input 0 is coming to q1 from q1 hence we
write
State = source state of input × input coming to it
Similarly,
q2 = q1 1 + q2 1
q3 = q2 0 + q3 (0+1)
Since the final states are q1 and q2, we are interested in solving q1 and q2 only. Let us see q1
first
q1 = q1 0 + ε
We can re-write it as
q1 = ε + q1 0
Which is similar to R = Q + RP, and gets reduced to R = OP*.
Assuming R = q1, Q = ε, P = 0
We get
q1 = ε.(0)*
q1 = 0* (ε.R*= R*)
 Substituting the value into q2, we will get
q2 = 0* 1 + q2 1
q2 = 0* 1 (1)* (R = Q + RP → Q P*)

The regular expression is given by

r = q1 + q2
= 0* + 0* 1.1*
r = 0* + 0* 1+ (1.1* = 1+)

1.11 Moore Machine: Moore machine is a finite state machine in which the next state is
decided by the current state and current input symbol. The output symbol at a given time
depends only on the present state of the machine. Moore machine can be described by 6 tuples
(Q, q0, ∑, O, δ, λ) where,

1. Q: finite set of states

2. q0: initial state of machine
3. ∑: finite set of input symbols
4. O: output alphabet
5. δ: transition function where Q × ∑ → Q
6. λ: output function where Q → O

Example 1: The state diagram for Moore Machine is

Transition table for Moore Machine is:

In the above Moore machine, the output is represented with each input state separated by /. The
output length for a Moore machine is greater than input by 1.

Input: 010
Transition: δ (q0,0) => δ(q1,1) => δ(q1,0) => q2
Output: 1110(1 for q0, 1 for q1, again 1 for q1, 0 for q2)

Example 2: Design a Moore machine to generate 1's complement of a given binary number.

Solution: To generate 1's complement of a given binary number the simple logic is that if the
input is 0 then the output will be 1 and if the input is 1 then the output will be 0. That means
there are three states. One state is start state. The second state is for taking 0's as input and
produces output as 1. The third state is for taking 1's as input and producing output as 0.

Hence the Moore machine will be,

For instance, take one binary number 1011 then

Input 1 0 1 1

State q0 q2 q1 q2 q2

Output 0 0 1 0 0

Thus we get 00100 as 1's complement of 1011, we can neglect the initial 0 and the output which
we get is 0100 which is 1's complement of 1011. The transaction table is as follows:
Thus Moore machine M = (Q, q0, ∑, O, δ, λ); where Q = {q0, q1, q2}, ∑ = {0, 1}, O = {0, 1}.
the transition table shows the δ and λ functions.

Example 3: Design a Moore machine for a binary input sequence such that if it has a substring
101, the machine output A, if the input has substring 110, it outputs B otherwise it outputs C.

Solution: For designing such a machine, we will check two conditions, and those are 101 and
110. If we get 101, the output will be A, and if we recognize 110, the output will be B. For other
strings, the output will be C.

The partial diagram will be:

Now we will insert the possibilities of 0's and 1's for each state. Thus the Moore machine
becomes:

Example 4: Construct a Moore machine that determines whether an input string contains an
even or odd number of 1's. The machine should give 1 as output if an even number of 1's are in
the string and 0 otherwise.

Solution: The Moore machine will be:

 This is the required Moore machine. In this machine, state q1 accepts an odd number of 1's and
state q0 accepts even number of 1's. There is no restriction on a number of zeros. Hence for 0
input, self-loop can be applied on both the states.

Example 5: Design a Moore machine with the input alphabet {0, 1} and output alphabet {Y, N}
which produces Y as output if input sequence contains 1010 as a substring otherwise, it produces
N as output.

Solution: The Moore machine will be:

1.12 Mealy Machine: A Mealy machine is a machine in which output symbol depends upon
the present input symbol and present state of the machine. In the Mealy machine, the output is
represented with each input symbol for each state separated by /. The Mealy machine can be
described by 6 tuples (Q, q0, ∑, O, δ, λ') where

1. Q: finite set of states

2. q0: initial state of machine
3. ∑: finite set of input alphabet
4. O: output alphabet
5. δ: transition function where Q × ∑ → Q
6. λ': output function where Q × ∑ →O

Example 1: Design a Mealy machine for a binary input sequence such that if it has a substring
101, the machine output A, if the input has substring 110, it outputs B otherwise it outputs C.
Solution: For designing such a machine, we will check two conditions, and those are 101 and
110. If we get 101, the output will be A. If we recognize 110, the output will be B. For other
strings the output will be C.

The partial diagram will be:

Now we will insert the possibilities of 0's and 1's for each state. Thus the Mealy machine
becomes:

Example 2: Design a mealy machine that scans sequence of input of 0 and 1 and generates
output 'A' if the input string terminates in 00, output 'B' if the string terminates in 11, and output
'C' otherwise.

Solution: The mealy machine will be:

1.13 Conversion from Mealy machine to Moore Machine

In Moore machine, the output is associated with every state, and in Mealy machine, the output is
given along the edge with input symbol. To convert Moore machine to Mealy machine, state
output symbols are distributed to input symbol paths. But while converting the Mealy machine to
Moore machine, we will create a separate state for every new output symbol and according to
incoming and outgoing edges are distributed.

The following steps are used for converting Mealy machine to the Moore machine:

Step 1: For each state(Qi), calculate the number of different outputs that are available in the
transition table of the Mealy machine.
Step 2: Copy state Qi, if all the outputs of Qi are the same. Break qi into n states as Qin, if it has
n distinct outputs where n = 0, 1, 2....
Step 3: If the output of initial state is 0, insert a new initial state at the starting which gives 1
output.

Example 1: Convert the following Mealy machine into equivalent Moore machine.

Solution: Transition table for above Mealy machine is as follows:

  For state q1, there is only one incident edge with output 0. So, we don't need to split this
state in Moore machine.
 For state q2, there is 2 incident edge with output 0 and 1. So, we will split this state into
two states q20( state with output 0) and q21(with output 1).
 For state q3, there is 2 incident edge with output 0 and 1. So, we will split this state into
two states q30( state with output 0) and q31( state with output 1).
 For state q4, there is only one incident edge with output 0. So, we don't need to split this
state in Moore machine.

Transition table for Moore machine will be:

Transition diagram for Moore machine will be:

Example 2: Convert the following Mealy machine into equivalent Moore machine.

Solution: Transition table for above Mealy machine is as follows:

The state q1 has only one output. The state q2 and q3 have both output 0 and 1. So we will create
two states for these states. For q2, two states will be q20(with output 0) and q21(with output 1).
Similarly, for q3 two states will be q30(with output 0) and q31(with output 1).

Transition table for Moore machine will be:

Transition diagram for Moore machine will be:

 1.14 Conversion from Moore machine to Mealy Machine

In the Moore machine, the output is associated with every state, and in the mealy machine, the
output is given along the edge with input symbol. The equivalence of the Moore machine and
Mealy machine means both the machines generate the same output string for same input string.

We cannot directly convert Moore machine to its equivalent Mealy machine because the length
of the Moore machine is one longer than the Mealy machine for the given input. To convert
Moore machine to Mealy machine, state output symbols are distributed into input symbol paths.
We are going to use the following method to convert the Moore machine to Mealy machine.

Method for conversion of Moore machine to Mealy machine

Let M = (Q, ∑, δ, λ, q0) be a Moore machine. The equivalent Mealy machine can be represented
by M' = (Q, ∑, δ, λ', q0). The output function λ' can be obtained as:

1. λ' (q, a) = λ(δ(q, a))

Example 1: Convert the following Moore machine into its equivalent Mealy machine.

Solution: The transition table of given Moore machine is as follows:

Q a b Output(λ)

q0 q0 q1 0

q1 q0 q1 1

The equivalent Mealy machine can be obtained as follows:

1. λ' (q0, a) = λ(δ(q0, a))

2. = λ(q0)
3. =0
4.
5. λ' (q0, b) = λ(δ(q0, b))
6. = λ(q1)
7. =1

The λ for state q1 is as follows:

1. λ' (q1, a) = λ(δ(q1, a))

2. = λ(q0)
3. =0
4.
5. λ' (q1, b) = λ(δ(q1, b))
6. = λ(q1)
7. =1

Hence the transition table for the Mealy machine can be drawn as follows:

The equivalent Mealy machine will be,

Example 2: Convert the given Moore machine into its equivalent Mealy machine.
 Solution: The transition table of given Moore machine is as follows:

Q a b Output(λ)

q0 q1 q0 0

q1 q1 q2 0

q2 q1 q0 1

The equivalent Mealy machine can be obtained as follows:

1. λ' (q0, a) = λ(δ(q0, a))

2. = λ(q1)
3. =0
4.
5. λ' (q0, b) = λ(δ(q0, b))
6. = λ(q0)
7. =0

The λ for state q1 is as follows:

1. λ' (q1, a) = λ(δ(q1, a))

2. = λ(q1)
3. =0
4.
5. λ' (q1, b) = λ(δ(q1, b))
6. = λ(q2)
7. =1
 The λ for state q2 is as follows:

1. λ' (q2, a) = λ(δ(q2, a))

2. = λ(q1)
3. =0
4.
5. λ' (q2, b) = λ(δ(q2, b))
6. = λ(q0)
7. =0

Hence the transition table for the Mealy machine can be drawn as follows:

The equivalent Mealy machine will be,

Example 3: Convert the given Moore machine into its equivalent Mealy machine.

Q a b Output(λ)
 q0 q0 q1 0

q1 q2 q0 1

q2 q1 q2 2

Solution: The transaction diagram for the given problem can be drawn as:

The equivalent Mealy machine can be obtained as follows:

1. λ' (q0, a) = λ(δ(q0, a))

2. = λ(q0)
3. =0
4.
5. λ' (q0, b) = λ(δ(q0, b))
6. = λ(q1)
7. =1

The λ for state q1 is as follows:

1. λ' (q1, a) = λ(δ(q1, a))

2. = λ(q2)
3. =2
4.
5. λ' (q1, b) = λ(δ(q1, b))
6. = λ(q0)
7. =0

The λ for state q2 is as follows:

1. λ' (q2, a) = λ(δ(q2, a))
2. = λ(q1)
3. =1
4.
5. λ' (q2, b) = λ(δ(q2, b))
6. = λ(q2)
7. =2

Hence the transition table for the Mealy machine can be drawn as follows:

The equivalent Mealy machine will be,

1.15 Pumping Lemma For Regular Grammars

 It gives a method for pumping (generating) many substrings from a given string.
 In other words, we say it provides means to break a given long input string into several
substrings.
 Lt gives necessary condition(s) to prove a set of strings is not regular.

Theorem:
Let L be a regular language. Then there exists a constant ‘c’ such that for every string w in L −
|w| ≥ c
We can break w into three strings, w = xyz, such that −
 |y| > 0
 |xy| ≤ c
 For all k ≥ 0, the string xykz is also in L.
1.15.1 Applications of Pumping Lemma
Pumping Lemma is to be applied to show that certain languages are not regular. It should never
be used to show a language is regular.
 If L is regular, it satisfies Pumping Lemma.
 If L does not satisfy Pumping Lemma, it is non-regular.
Method to prove that a language L is not regular
 At first, we have to assume that L is regular.
 So, the pumping lemma should hold for L.
 Use the pumping lemma to obtain a contradiction −
 Select w such that |w| ≥ c
 Select y such that |y| ≥ 1
 Select x such that |xy| ≤ c
 Assign the remaining string to z.
 Select k such that the resulting string is not in L.
Hence L is not regular.
Problem: Prove that L = {aibi | i ≥ 0} is not regular.
Solution −
 At first, we assume that L is regular and n is the number of states.
 Let w = anbn. Thus |w| = 2n ≥ n.
 By pumping lemma, let w = xyz, where |xy| ≤ n.
 Let x = ap, y = aq, and z = arbn, where p + q + r = n, p ≠ 0, q ≠ 0, r ≠ 0. Thus |y| ≠ 0.
 Let k = 2. Then xy2z = apa2qarbn.
 Number of as = (p + 2q + r) = (p + q + r) + q = n + q
 Hence, xy2z = an+q bn. Since q ≠ 0, xy2z is not of the form anbn.
 Thus, xy2z is not in L. Hence L is not regular.

1.16 Minimization of DFA using Myhill-Nerode Theorem:

Minimization of DFA is Required to obtain the minimal and equivalent version of any DFA
which consists of minimum number of states possible. Myhill-Nerode theorem can be used to
convert a DFA to its equivalent DFA with minimum no of states. This method of minimization is
also called Table filling method. There is also another method called Partitioning Method or
Equivalence Method for the minimization of DFA.
Steps for the Minimization of DFA:
1. Create the pairs of all the states involved in the given DFA.
2. Mark all the pairs (Qa,Qb) such a that Qa is Final state and Qb is Non-Final State.
3. If there is any unmarked pair (Qa,Qb) such a that δ(Qa,x) and δ(Qb,x) is marked, then mark
(Qa,Qb). Here x is a input symbol. Repeat this step until no more marking can be made.
4. Combine all the unmarked pairs and make them a single state in the minimized DFA.

Example: Consider the following DFA,

Following is the transition table for the above DFA

Minimizing the above DFA using Myhill-Nerode Theorem :

Step-1: Create the pairs of all the states involved in DFA.
Step-2: Mark all the pairs (Qa,Qb) such a that Qa is Final state and Qb is Non-Final State.

Step-3: If there is any unmarked pair (Qa,Qb) such a that δ(Qa,x) and δ(Qb,x) is marked, then
mark (Qa,Qb). Here x is a input symbol. Repeat this step until no more marking can be made.
 Check for the unmarked pair Q2,Q1
 Check when x=0 : δ(Q2,0) = Q4 and δ(Q1,0) = Q3, check if the pair Q4,Q3 is
marked and no it is not marked.
 Check when x=1 : δ(Q2,1) = Q3 and δ(Q1,1) = Q4, check if the pair Q4,Q3 is
marked and no it is not marked.
 Hence we cannot mark the pair Q2,Q1.
 Check for the unmarked pair Q3,Q0
 Check when x=0 : δ(Q3,0) = Q5 and δ(Q0,0) = Q1, check if the pair Q5,Q1 is
marked and no it is not marked.
 Check when x=1 : δ(Q3,1) = Q5 and δ(Q0,1) = Q2, check if the pair Q5,Q2 is
marked and no it is not marked.
 Hence we cannot mark the pair Q3,Q0.
 Check for the unmarked pair Q4,Q0
 Check when x=0 : δ(Q4,0) = Q5 and δ(Q0,0) = Q1, check if the pair Q5,Q1 is
marked and no it is not marked.
 Check when x=1 : δ(Q4,1) = Q5 and δ(Q0,1) = Q2, check if the pair Q5,Q2 is
marked and no it is not marked.
 Hence we cannot mark the pair Q4,Q0.
 Check for the unmarked pair Q4,Q3
 Check when x=0 : δ(Q4,0) = Q5 and δ(Q3,0) = Q5, Such pair of state Q5,Q5 don’t
exists.
 Check when x=1 : δ(Q4,1) = Q5 and δ(Q3,1) = Q5, Such pair of state Q5,Q5 don’t
exists.
 Hence we cannot mark the pair Q4,Q3.
 Check for the unmarked pair Q5,Q1
 Check when x=0 : δ(Q5,0) = Q5 and δ(Q1,0) = Q3, check if the pair Q5,Q3 is
marked and yes it is marked.
 Hence we can mark the pair Q5,Q1.

 Check for the unmarked pair Q5,Q2

 Check when x=0 : δ(Q5,0) = Q5 and δ(Q2,0) = Q4, check if the pair Q5,Q4 is
marked and yes it is marked.
 Hence we can mark the pair Q5,Q2.

 We have checked for all the unmarked pairs but don’t need to stop here we need to continue
this process until no more markings can be made.
 Check for the unmarked pair Q2,Q1
 Check when x=0 : δ(Q2,0) = Q4 and δ(Q1,0) = Q3, check if the pair Q4,Q3 is
marked and no it is not marked.
 Check when x=1 : δ(Q2,1) = Q3 and δ(Q1,1) = Q4, check if the pair Q4,Q3 is
marked and no it is not marked.
 Hence we cannot mark the pair Q2,Q1.
 Check for the unmarked pair Q3,Q0
 Check when x=0 : δ(Q3,0) = Q5 and δ(Q0,0) = Q1, check if the pair Q5,Q1 is
marked and yes it is marked.
 Hence we can mark the pair Q3,Q0.

 Check for the unmarked pair Q4,Q0

 Check when x=0 : δ(Q4,0) = Q5 and δ(Q0,0) = Q1, check if the pair Q5,Q1 is
marked and yes it is marked.
 Hence we cannot mark the pair Q4,Q0.

 Check for the unmarked pair Q4,Q3

 Check when x=0 : δ(Q4,0) = Q5 and δ(Q3,0) = Q5, Such pair of state Q5,Q5 don’t
exists.
 Check when x=1 : δ(Q4,1) = Q5 and δ(Q3,1) = Q5, Such pair of state Q5,Q5 don’t
exists.
 Hence we cannot mark the pair Q4,Q3.
 Now even though we repeat the procedure we cannot mark the pairs Q2,Q1(since Q4,Q3 is
not marked) and Q4,Q3(since Q5,Q5 such pair of states does not exists.). Hence we stop here.

Step-4: Combine all the unmarked pairs and make them as a single state in the minimized DFA.
 The unmarked Pairs are Q2,Q1 and Q4,Q3 hence we combine them.
Following is the Minimized DFA with Q1Q2 and Q3Q4 as the combined states.
 Q0 remains as our starting state.
 Q1 and Q2 were our final states so even we combine them they will remain as the combined
final state.
 Q5 is the another final state we have.
 If we check the original Transition Table
 δ(Q0,0) was Q1 and δ(Q1,1) was Q2. As the states are combined, the transition of
Q0 on both the inputs 0 and 1 will be to the state Q1Q2.
 δ(Q1,0) was Q3, δ(Q1,1) was Q4 and δ(Q2,0) was Q4, δ(Q1,1) was Q3. As the
states are combined, the transition of Q1Q2 on both the inputs 0 and 1 will be to
the state Q3Q4.
 δ(Q3,0) was Q5, δ(Q3,1) was Q5 and δ(Q4,0) was Q5, δ(Q4,1) was Q5. As the
states are combined, the transition of Q3Q4 on both the inputs 0 and 1 will be to
the state Q5.
 δ(Q5,0) was Q5 and δ(Q5,1) was Q5. Hence the transition of state Q5 on both the
inputs will be to the state Q5 itself.
Transition table for Minimized DFA