Theory of Computation Prepared By: Er.

Inderjeet Singh (e8822)

Topics To Be Covered:

UNIT –II

Properties of Regular sets: The Pumping Lemma for Regular sets, Application of the
Pumping Lemma, Closure Properties of Regular Sets, Myhill- Nerode Theorem and
Minimization of Finite Automata, Minimization Algorithm.

Finite Automata with output: Moore and Mealy Machines. Equivalence of Moore and Mealy
Machines.

Context Free Grammars: Examples and Definitions, Derivation trees and ambiguity, An
Unambiguous CFG for Algebraic Expressions. Regular Grammar, Simplified forms and Normal
forms: Removal of useless symbols and unit production, Removal of Λ-moves, Chomsky
Normal Form (CNF), Griebach Normal Form (GNF).

Computer Science and Engineering Page 1

 Theory of Computation Prepared By: Er. Inderjeet Singh (e8822)

Unit -2
Properties of Regular Sets

Pumping lemma for Regular languages

 To prove that some languages cannot be regular.

 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.
 It gives necessary condition(s) to prove a set of strings is not regular.

Theorem: For any regular language L, there exists an integer P(pumping lemma), such that
for all w in L

|w|>=P

We can break w into three strings, w=xyz such that.

(1) |xy| < P

(2) |y| > 0

(3) For all k>= 0: the string xykz is also in L

Computer Science and Engineering Page 2

 Theory of Computation Prepared By: Er. Inderjeet Singh (e8822)

Computer Science and Engineering Page 3

 Theory of Computation Prepared By: Er. Inderjeet Singh (e8822)

Computer Science and Engineering Page 4

 Theory of Computation Prepared By: Er. Inderjeet Singh (e8822)

Computer Science and Engineering Page 5

 Theory of Computation Prepared By: Er. Inderjeet Singh (e8822)

Example:

Computer Science and Engineering Page 6

 Theory of Computation Prepared By: Er. Inderjeet Singh (e8822)

Computer Science and Engineering Page 7

 Theory of Computation Prepared By: Er. Inderjeet Singh (e8822)

Closure Properties of Regular Sets

Closure property: If a set of regular languages are combined using an operator, then the resulting language is
also regular.

Regular languages are closed under:

– Union, intersection, complement, difference

– Reversal

– Kleene closure

– Concatenation

– Homomorphism

– Inverse homomorphism

1. Regular Languages are closed under UNION:

IF L and M are two RLs THEN:
they both have two corresponding regular expressions, R and S respectively
(L U M) can be represented using the regular expression R+S
Therefore, (L U M) is also regular
2. Regular Languages are closed under COMPLEMENT:
If L is an RL over ∑, then L=∑*-L
To show L is also regular, make the following construction
Hint: Convert every final state into non-final, and every non-final state into a final state.

Computer Science and Engineering Page 8

 Theory of Computation Prepared By: Er. Inderjeet Singh (e8822)

3. Regular languages are closed under Intersection: Since we know RLs are closed under union and
complementation, they are also closed under intersection. A more direct way would be construct a finite
automaton for L ∩ M.

4. Regular Languages are closed under SET Difference:

Computer Science and Engineering Page 9

 Theory of Computation Prepared By: Er. Inderjeet Singh (e8822)

5. Regular Languages are closed under reversal of a language

Computer Science and Engineering Page 10

 Theory of Computation Prepared By: Er. Inderjeet Singh (e8822)

Computer Science and Engineering Page 11

 Theory of Computation Prepared By: Er. Inderjeet Singh (e8822)

Computer Science and Engineering Page 12

 Theory of Computation Prepared By: Er. Inderjeet Singh (e8822)

DFA Minimization using MyHill-Nerode Theorem

Algorithm Steps:

Step 1 − Draw a table for all pairs of states (Qi, Qj) not necessarily connected directly [All are unmarked
initially]

Step 2 − Consider every state pair (Qi, Qj) in the DFA where Qi ∈ F and Qj ∉ F or vice versa and mark them.
[Here F is the set of final states]

Step 3 − Repeat this step until we cannot mark anymore states −

If there is an unmarked pair (Qi, Qj), mark it if the pair {δ (Qi, A), δ (Qi, A)} is marked for some input alphabet.

Step 4 − Combine all the unmarked pair (Qi, Qj) and make them a single state in the reduced DFA.

Example: Let us use Algorithm 2 to minimize the DFA shown below.

Computer Science and Engineering Page 13

 Theory of Computation Prepared By: Er. Inderjeet Singh (e8822)

Step 3 − We will try to mark the state pairs, with green colored check mark, transitively. If we input 1 to state ‘a’ and ‘f’,
it will go to state ‘c’ and ‘f’ respectively. (c, f) is already marked, hence we will mark pair (a, f). Now, we input 1 to state
‘b’ and ‘f’; it will go to state ‘d’ and ‘f’ respectively. (d, f) is already marked, hence we will mark pair (b, f).

Computer Science and Engineering Page 14

 Theory of Computation Prepared By: Er. Inderjeet Singh (e8822)

Hint:

After step 3, we have got state combinations {a, b} {c, d} {c, e} {d, e} that are unmarked.

We can recombine {c, d} {c, e} {d, e} into {c, d, e}

Hence we got two combined states as − {a, b} and {c, d, e}

So the final minimized DFA will contain three states {f}, {a, b} and {c, d, e}

Computer Science and Engineering Page 15

 Theory of Computation Prepared By: Er. Inderjeet Singh (e8822)

DFA Minimization using Equivalence Theorem

If X and Y are two states in a DFA, we can combine these two states into {X, Y} if they are not distinguishable.
Two states are distinguishable, if there is at least one string S, such that one of δ (X, S) and δ (Y, S) is accepting
and another is not accepting. Hence, a DFA is minimal if and only if all the states are distinguishable.

Steps for Algorithm

Step 1 − All the states Q are divided in two partitions − final states and non-final states and are denoted by P0.
All the states in a partition are 0th equivalent. Take a counter k and initialize it with 0.

Computer Science and Engineering Page 16

 Theory of Computation Prepared By: Er. Inderjeet Singh (e8822)

Step 2 − Increment k by 1. For each partition in Pk, divide the states in Pk into two partitions if they are k-
distinguishable. Two states within this partition X and Y are k-distinguishable if there is an input S such that
δ(X, S) and δ(Y, S) are (k-1)-distinguishable.

Step 3 − If Pk ≠ Pk-1, repeat Step 2, otherwise go to Step 4.

Step 4 − Combine kth equivalent sets and make them the new states of the reduced DFA.

Computer Science and Engineering Page 17

 Theory of Computation Prepared By: Er. Inderjeet Singh (e8822)

Computer Science and Engineering Page 18

 Theory of Computation Prepared By: Er. Inderjeet Singh (e8822)

Computer Science and Engineering Page 19

 Theory of Computation Prepared By: Er. Inderjeet Singh (e8822)

Computer Science and Engineering Page 20

 Theory of Computation Prepared By: Er. Inderjeet Singh (e8822)

Computer Science and Engineering Page 21

 Theory of Computation Prepared By: Er. Inderjeet Singh (e8822)

Chapter -2 Finite Automata with Output

Moore Machines

Computer Science and Engineering Page 22

 Theory of Computation Prepared By: Er. Inderjeet Singh (e8822)

General Representation of Moore Machines by table

Mealy Machine

Computer Science and Engineering Page 23

 Theory of Computation Prepared By: Er. Inderjeet Singh (e8822)

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.

Computer Science and Engineering Page 24

 Theory of Computation Prepared By: Er. Inderjeet Singh (e8822)

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

Computer Science and Engineering Page 25

 Theory of Computation Prepared By: Er. Inderjeet Singh (e8822)

Computer Science and Engineering Page 26

 Theory of Computation Prepared By: Er. Inderjeet Singh (e8822)

Example 2: Convert the following Mealy Machine into Moore Machine?

Computer Science and Engineering Page 27

 Theory of Computation Prepared By: Er. Inderjeet Singh (e8822)

Solution:

Example 3:

Computer Science and Engineering Page 28

 Theory of Computation Prepared By: Er. Inderjeet Singh (e8822)

Solution:

Computer Science and Engineering Page 29

 Theory of Computation Prepared By: Er. Inderjeet Singh (e8822)

Solution

Computer Science and Engineering Page 30

 Theory of Computation Prepared By: Er. Inderjeet Singh (e8822)

Conversion from Moore to Mealy Machine

Computer Science and Engineering Page 31

 Theory of Computation Prepared By: Er. Inderjeet Singh (e8822)

Example:

Computer Science and Engineering Page 32

 Theory of Computation Prepared By: Er. Inderjeet Singh (e8822)

Solution

Example

Computer Science and Engineering Page 33

 Theory of Computation Prepared By: Er. Inderjeet Singh (e8822)

Solution

Computer Science and Engineering Page 34

 Theory of Computation Prepared By: Er. Inderjeet Singh (e8822)

Example: Moore machine to Mealy through Transition Diagram

Solution

Computer Science and Engineering Page 35

 Theory of Computation Prepared By: Er. Inderjeet Singh (e8822)

Chapter 3: Context Free Grammers

Context Free Grammars: Examples and Definitions, Derivation trees and ambiguity, An Unambiguous CFG
for Algebraic Expressions. Regular Grammar, Simplified forms and Normal forms: Removal of useless symbols
and unit production, Removal of Λ-moves, Chomsky Normal Form (CNF), Griebach Normal Form (GNF).

Computer Science and Engineering Page 36

 Theory of Computation Prepared By: Er. Inderjeet Singh (e8822)

Computer Science and Engineering Page 37

 Theory of Computation Prepared By: Er. Inderjeet Singh (e8822)

Computer Science and Engineering Page 38

 Theory of Computation Prepared By: Er. Inderjeet Singh (e8822)

Computer Science and Engineering Page 39

 Theory of Computation Prepared By: Er. Inderjeet Singh (e8822)

Computer Science and Engineering Page 40

 Theory of Computation Prepared By: Er. Inderjeet Singh (e8822)

Computer Science and Engineering Page 41

 Theory of Computation Prepared By: Er. Inderjeet Singh (e8822)

Computer Science and Engineering Page 42

 Theory of Computation Prepared By: Er. Inderjeet Singh (e8822)

Computer Science and Engineering Page 43

 Theory of Computation Prepared By: Er. Inderjeet Singh (e8822)

Example 1:

Example 2

Example 3

Computer Science and Engineering Page 44

 Theory of Computation Prepared By: Er. Inderjeet Singh (e8822)

Example 4(Left)

Computer Science and Engineering Page 45

 Theory of Computation Prepared By: Er. Inderjeet Singh (e8822)

Computer Science and Engineering Page 46

 Theory of Computation Prepared By: Er. Inderjeet Singh (e8822)

Computer Science and Engineering Page 47

 Theory of Computation Prepared By: Er. Inderjeet Singh (e8822)

Example:

Example:

Solution

Pick the start state A and output is on symbol ‘a’ going to state B

A→aB

Now we will pick state B and then we will go on each output

i.e B→aB

B→bB, B→ε

Computer Science and Engineering Page 48

 Theory of Computation Prepared By: Er. Inderjeet Singh (e8822)

Therefore,

Final right linear grammar is as follows − A→aB B→aB/bB/ε

Computer Science and Engineering Page 49

 Theory of Computation Prepared By: Er. Inderjeet Singh (e8822)

Computer Science and Engineering Page 50

 Theory of Computation Prepared By: Er. Inderjeet Singh (e8822)

Type Grammar Accepted Language Accepted Automaton

Type 0 Unrestricted grammar Recursively enumerable language Turing Machine
Type 1 Context-sensitive Context-sensitive language Linear-bounded automaton
grammar
Type 2 Context-free grammar Context-free language Pushdown automaton
Type 3 Regular grammar Regular language Finite state automaton

Computer Science and Engineering Page 51

 Theory of Computation Prepared By: Er. Inderjeet Singh (e8822)

Type 0: Unrestricted Grammar:

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.

In type 0 there must be at least one variable on the Left side of production.

For example: Here, Variables are S, A, B,C and Terminals a, b, s.

Sab --> ba
A --> S
sABC--> sBC

Type 1: Context-Sensitive Grammar or Non-contracting 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

Computer Science and Engineering Page 52

 Theory of Computation Prepared By: Er. Inderjeet Singh (e8822)

Also,

2nd Definition:

Computer Science and Engineering Page 53

 Theory of Computation Prepared By: Er. Inderjeet Singh (e8822)

Note: The rule of the form A → ε is not allowed unless A is a start symbol. It does not occur on
the right-hand side of any rule.

Type 2: Context-Free Grammar:

Type-2 grammars generate context-free languages. The language generated by the grammar is recognized by a
pushdown 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 right handside.

Formal Definition

For example:

S --> AB
A --> a
B --> b

Computer Science and Engineering Page 54

 Theory of Computation Prepared By: Er. Inderjeet Singh (e8822)

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.

X → a | aY
Y → b

Formal Definition

Computer Science and Engineering Page 55

 Theory of Computation Prepared By: Er. Inderjeet Singh (e8822)

Computer Science and Engineering Page 56

 Theory of Computation Prepared By: Er. Inderjeet Singh (e8822)

Computer Science and Engineering Page 57

 Theory of Computation Prepared By: Er. Inderjeet Singh (e8822)

Computer Science and Engineering Page 58

 Theory of Computation Prepared By: Er. Inderjeet Singh (e8822)

Computer Science and Engineering Page 59

 Theory of Computation Prepared By: Er. Inderjeet Singh (e8822)

Computer Science and Engineering Page 60

 Theory of Computation Prepared By: Er. Inderjeet Singh (e8822)

Computer Science and Engineering Page 61

 Theory of Computation Prepared By: Er. Inderjeet Singh (e8822)

Computer Science and Engineering Page 62

 Theory of Computation Prepared By: Er. Inderjeet Singh (e8822)

Computer Science and Engineering Page 63

 Theory of Computation Prepared By: Er. Inderjeet Singh (e8822)

Computer Science and Engineering Page 64

 Theory of Computation Prepared By: Er. Inderjeet Singh (e8822)

Computer Science and Engineering Page 65

 Theory of Computation Prepared By: Er. Inderjeet Singh (e8822)

Example:

Computer Science and Engineering Page 66

 Theory of Computation Prepared By: Er. Inderjeet Singh (e8822)

Computer Science and Engineering Page 67

 Theory of Computation Prepared By: Er. Inderjeet Singh (e8822)

Computer Science and Engineering Page 68

 Theory of Computation Prepared By: Er. Inderjeet Singh (e8822)

Computer Science and Engineering Page 69

 Theory of Computation Prepared By: Er. Inderjeet Singh (e8822)

Computer Science and Engineering Page 70

 Theory of Computation Prepared By: Er. Inderjeet Singh (e8822)

Computer Science and Engineering Page 71

 Theory of Computation Prepared By: Er. Inderjeet Singh (e8822)

Computer Science and Engineering Page 72

 Theory of Computation Prepared By: Er. Inderjeet Singh (e8822)

Computer Science and Engineering Page 73

 Theory of Computation Prepared By: Er. Inderjeet Singh (e8822)

Computer Science and Engineering Page 74

 Theory of Computation Prepared By: Er. Inderjeet Singh (e8822)

Reduction to Chomsky Normal Form

Computer Science and Engineering Page 75

 Theory of Computation Prepared By: Er. Inderjeet Singh (e8822)

Computer Science and Engineering Page 76

 Theory of Computation Prepared By: Er. Inderjeet Singh (e8822)

Computer Science and Engineering Page 77

 Theory of Computation Prepared By: Er. Inderjeet Singh (e8822)

Computer Science and Engineering Page 78

 Theory of Computation Prepared By: Er. Inderjeet Singh (e8822)

Computer Science and Engineering Page 79

 Theory of Computation Prepared By: Er. Inderjeet Singh (e8822)

Computer Science and Engineering Page 80

 Theory of Computation Prepared By: Er. Inderjeet Singh (e8822)

Computer Science and Engineering Page 81

 Theory of Computation Prepared By: Er. Inderjeet Singh (e8822)

Computer Science and Engineering Page 82

 Theory of Computation Prepared By: Er. Inderjeet Singh (e8822)

Computer Science and Engineering Page 83

 Theory of Computation Prepared By: Er. Inderjeet Singh (e8822)

Then removal of Left Recursion

Computer Science and Engineering Page 84