The two states C and D are equivalent.

Similarly state B and C are equivalent

B = C = D.

The minimized DFA will then be

Example 5: Convert the following ε - NFA to NFA and then convert the resultant NFA to DFA.

Solution: Conversion of NFA to NFA

We will obtain ɛ - closure of each state

ε - closure (A) = {A, B, C}

ε - closure (B) = {B, C}

ε - closure (C) = {C}

ε - closure (D) = {D}

Now we will obtain δ' transitions for each state on each input symbol.

δ' (A, 0) = ε - closure (δ (ε - closure(A), 0))

= ε - closure (δ ((A, B, C), 0))

= ε - closure (δ (A, 0) U δ (B, 0), U δ (C,0))

= ε - closure (ϕ U ϕ U ϕ)

=ϕ

δ' (A, 0) = ϕ

δ' (A, 1) = ε - closure (δ (ε - closure(A), 1))

= ε - closure (δ (A, B, C), 1)

= ε - closure (A, D, C)

= ε - closure (A) U ε - closure (D) U ε - closure (C)

= {A, B, C, D}

δ' (A, 1) = {A, B, C, D}

δ' (B, 0) = ε - closure (δ (ε - closure (B), 0))

= ε - closure (δ (B, C), 0)

δ' (B, 0) = ϕ

δ' (B, 1) = ε - closure (δ (ε - closure (B), 1))

= ε - closure (δ ((B, C), 1)

= ε - closure (D, C)

= ε - closure (D) U ε - closure(C)

=DUC

= {D, C}

δ' (B, 1) = {D, C}

δ' (C, 0) = ε - closure(δ (ε - closure(C), 0)

= ε - closure (δ (C, 0)

= ε - closure (ϕ)

δ' (C, 0) = ϕ

δ' (C, 1) = ε - closure (δ (ε - closure (C), 1)

= ε - closure (δ (C, 1)

= ε - closure (C)

= {C}

δ' (C, 1) = C

δ' (D, 0) = ε closure (δ (ε - closure(D), 0))

= ε - closure (δ (D, 0)

= ε - closure (B)

δ' (D, 0) = (B, C)

δ' (D, 1) = ε - closure (8 (e-closure(D), 1))

= ε - closure (δ (D, 1)

= ε - closure (ϕ)

δ' (D, 1) = ϕ

The transition table will be

The NFA will be:

Conversion of NFA to DFA

δ (A, 0) = 0

δ (A, 1) = {A, B, C, D} → call it as state P

δ (A, 1) = p

δ (P, 0) = P

= δ ((A, B, C, D), 0)

= δ (A, 0) U δ (B, 0) U δ (C, 0) U δ (D, 0)

{B, C} → call it as state Q

S (P, 0) = Q

δ (P, 1) = δ ((A, B, C, D), 1)

= δ (A, 1) U δ (B, 1) U δ (C, 1) U δ (D, 1)

= {A, B, C, D}

δ (P,1) = P

δ (Q, 0) = δ ((B, C,), 0)

= δ (B, 0) U δ (C, 0)

δ (Q, 0) = ϕ

δ (Q, 1) = ((B, C), 1)

= δ (B, 1) U δ (C, 1)

= {C, D} U {C}

= {C, D} → call it as state R

δ (Q, 1) = R

δ (R, 0) = {δ (C, D), 0}

= {B, C}

δ (R, 0) = Q

δ (R, 1) = δ ((C, D), 1)

δ (R, 1) = {C}

δ (C, 0) = ϕ
δ (C, 1) = C

The transition table will be

REGULAR EXPRESSION TO FINITE AUTOMATA

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 ε.

Minimization or Reduction Method

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:
 ARDEN’S THEOREM

In order to find out a regular expression of a Finite Automaton, we use Arden’s Theorem along with the
properties of regular expressions.

Statement −

Let P and Q be two regular expressions.

If P does not contain null string, then R = Q + RP has a unique solution that is R = QP*

Proof −

R = Q + (Q + RP)P [After putting the value R = Q + RP]

= Q + QP + RPP

When we put the value of R recursively again and again, we get the following equation −

R = Q + QP + QP2 + QP3…..

R = Q (ε + P + P2 + P3 + …. )

R = QP* [As P* represents (ε + P + P2 + P3 + ….) ]

Hence, proved.

Assumptions for Applying Arden’s Theorem

The transition diagram must not have NULL transitions

It must have only one initial state

Method

Step 1 − Create equations as the following form for all the states of the DFA having n states with initial state
q1.

q1 = q1R11 + q2R21 + … + qnRn1 + ε

q2 = q1R12 + q2R22 + … + qnRn2

…………………………

qn = q1R1n + q2R2n + … + qnRnn

Rij represents the set of labels of edges from qi to qj, if no such edge exists, then Rij = ∅

Step 2 − Solve these equations to get the equation for the final state in terms of Rij

Problem

Construct a regular expression corresponding to the automata given below −

Solution −

Here the initial state and final state is q1.

The equations for the three states q1, q2, and q3 are as follows −

q1 = q1a + q3a + ε (ε move is because q1 is the initial state0

q2 = q1b + q2b + q3b

q3 = q2a

Now, we will solve these three equations −

q2 = q1b + q2b + q3b

= q1b + q2b + (q2a)b (Substituting value of q3)

= q1b + q2(b + ab)

= q1b (b + ab)* (Applying Arden’s Theorem)

q1 = q1a + q3a + ε

= q1a + q2aa + ε (Substituting value of q3)

= q1a + q1b(b + ab*)aa + ε (Substituting value of q2)

= q1(a + b(b + ab)*aa) + ε

= ε (a+ b(b + ab)*aa)*

= (a + b(b + ab)*aa)*

Hence, the regular expression is (a + b(b + ab)*aa)*.

Problem

Construct a regular expression corresponding to the automata given below −

Solution −

Here the initial state is q1 and the final state is q2

Now we write down the equations −

q1 = q10 + ε

q2 = q11 + q20

q3 = q21 + q30 + q31

Now, we will solve these three equations −

q1 = ε0* [As, εR = R]

So, q1 = 0*
q2 = 0*1 + q20

So, q2 = 0*1(0)* [By Arden’s theorem]

Hence, the regular expression is 0*10*.

Conversion of Finite Automata to Regular Expressions

The Arden's theorem is useful for checking the equivalence of two regular expression as well as in conversion
of DFA to r.e. Let us see its use in conversion of DFA to r.e.

Following algorithm is used to build the r.e. from 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 qj such that

qi = αji qj

If qi is a start state

to qi

qi = αji qj + ε

5. Similarly compute the final state which ultimately gives the regular expression r.

Let us solve few examples based on this algorithm.

Example 1. Construct r.e. from given DFA.

Solution: Let us write down the equations state on

q1 = q1 a + ε

Since q1 is a start state ε will be added and the input a is coming to q1 from q1 hence we write

State = Input coming to it × Source state of input

Similarly q2 = q1 a + q2 b
Let us simplify q1 first

q1 = q1 a + ε

We can re-write it as

q1 = ε + q1 a

which is similar to R = Q + RP which further gets reduced to R = QP*.

Assuming R = q1, Q = ε, p = a

We get

q1 = ε . a*

q1 = a*

εR=R

Substituting value of q1 in q2 we get

q2 = q1 b + q2 b

q2 = a * b + q2 b

We can compare this equation with R = Q + R P assuming R = q2, Q = a*b, P = b which gets reduced to R =
QP*.

q2 = a*b.b*

As R R* = R+

q2 = a*.b+

From the given DFA, if we want to find out the regular expression, we normally calculate the equation for
final state. Since in the given DFA q2 is a final state and q2 = a*b+. We can conclude as the DFA represents a
as regular expression.

Example 2. Represent the language accepted by following DFA.

Solution: Since there is only one state in the finite automata let us solve for q0 only.

q0 = q00 + q01 + ε

q0 = q0 (0+1) + ε
= ε . (0+1)* R=Q+RP

q0 = (0+1)*

Since q0 is a final state, q0 represents the final r.e. as

r = (0 + 1)*

L (r) = {ε, 0,00,1,11,10,....}

L (r) = {any combination of 0 and 1}

Example 3 Construct r.e. for the given DFA.

Solution: Let us build the regular expression for each state.

q1 = q10 + ε

q2 = q11 + q21

q3 = q20 + q3 (0 + 1)

Since final states are q1 and q2, we are interested in solving q1 and q2 only.

Let us see q1 first

q1 = ε + q10

Which is R = Q + R P equivalent so we can write

q1 = ε .(0)*

q1 = 0*

ε. R = R

Substituting this value into q2, we will get

q2 = 0*1 + q21

q2 = 0*1 (1)* R = Q + R P ⇒ Q P*

The regular expression is given by

r = q1 + q2 =0* + 0* 1. 1*
r = 0* + 0* 1+ 1.1* = 1+

Example 4 Convert the following NFA into a regular expression.

Solution: We will obtain regular expression using Arden's method.

The equations for each state are -

A = A0 + A1 + ε = A(0 + 1) + ε

B = A1

C = B (0+1)

D = C (0+1)

We will solve equation (1)

A = A (0+1) + ε

i) R = RP + Q gives R = QP* ii) εR* = R*

A = ε(0+1)* = (0+1)*

A = (0+1)* … (5)

Equation (2) becomes

B = A1 = (0+1)* 1 … (6)

Now by using equation (6) we get equation (3) as

C = B (0+1)

C = (0+1)* 1 (0+1) … (7)

Using equation (7), we get equation (4) as

D = C (0+1)

= (0+1)* 1 (0+1) (0+1) … (8)

As state C and D are final states equation (7) and equation (8) represent final regular expression.

r.e. [(0+1)* 1 (0 + 1)] + [(0+1)* 1 (0 + 1) (0 + 1)]

Example 5 Construct the regular expression corresponding to the state diagram given in the following Fig.
2.4.5.

Solution: We will obtain the regular expression for the given state diagram using Arden's theorem. Let us
write equations for each state.

q1 = q10 + q30 + ε being a start state, add ɛ.

q2 = q11 + q21 + q31

q3 = q20

Consider q2 first.

q2 = q11 + q21 + q31

q2 = q11 + q21 + q201 q3 = q20

q2 = q2 (1+01) + q11

R = Q + RP gives R = QP*

R = q2, Q = q11, P = (1 + 01)

q2 = q11 (1+01)*

Then put value of q2 in q3 and we get,

q3 = q11 (1+01)* 0

Now substitute value of q3 in q1

q1 = q10 + q30 + ε

q1 = q10 + q11 (1+01)* 00 + ε

q1 = q1 [0+1 (1+01)* 00] + ε

R = Q + RP gives R = QP*

R = q1, Q = ε, P = 0+1 (1+01)* 00 we get

q1 = ε [0+1 (1+01)* 00]*

q1 = (0+1 (1+01)* 00)* εR=R

State q1 is a final state. Hence an equation for final state becomes a regular expression for given state
diagram.

The r.e. = (0+1 (1+01)* 00)*

Example 6. Obtain the regular expression for the finite automata.

Solution: We will write the equations for each state,

q1 = q1 a + ε … (1)

q2 = q2a + q1b … (2)

q3 = q2b … (3)

Solving equation (1)

q1 = q1 a + ε

q1 = ε a* = a*

R = Q + RP

gives R = QP*

and ε R* = R*

Solving equation (2) using q1 = a* we get,

q2 = q2 a + a* b

q2 = a* b a*

Solving q3 by putting q2 = a* b a*

we get

q3 = q2 b

q3 = a* ba* b

As q3 represents the final state, the equation for state q3 represents the regular expression. Hence regular
expression = a* ba* b.
PUMPING LEMMA FOR REGULAR EXPRESSIONS

concept of pumping lemma. Pumping lemma can be used for regular languages and context free languages.

Here most importantly, we will see the regular languages and pumping lemma on it. For the context, let's start
with the regular languages then jump to the pumping lemma with examples for a better understanding.

Pumping lemma is a basic and important theorem used for checking whether given string is accepted by
regular expression or not. In short, this lemma tells us whether given language is regular or not.

• One key them is that any language for which it is possible to design the finite automata is definitely the
regular language.

What are Regular Languages?

We have crossed a long journey on regular languages. For a recap, regular languages are a special kind of
language that can be recognized by a finite automaton. Think of a finite automaton as a machine with a finite
memory. It reads symbols from an input string one at a time and uses its limited memory to decide whether
the string belongs to the language.

For example, consider the language of all strings over the alphabet {a, b} that end with 'aa'. This language is
regular because we can construct a finite automaton with two states: one for the initial state and another for a
state that indicates the presence of 'aa'.

Why Do We Need the Pumping Lemma?

The pumping lemma is a way to prove that a language is not regular. It provides a powerful way to show that
no finite automaton can recognize a language, even if we can't explicitly construct one.

The lemma essentially states that if a language is regular, then any sufficiently long string in the language can
be pumped meaning a substring can be repeated an arbitrary number of times, and the resulting string will
still be in the language.

It is little bit confusing. Let us see the lemma first and then understand through example.

The Steps for Pumping Lemma

Let's break down the pumping lemma step-by-step −

Step 1: Consider a language as regular

To begin with this lemma, we start by assuming that the language we want to analyse is regular. This
assumption will eventually lead to a contradiction if the language is indeed not regular.

Step 2: Assume a constant C and select a string W

We need to select a constant 'C' and a string 'W' from the language. Now the string 'W' should have a length
greater than or equal to the constant 'C'. Here this constant 'C' represents the maximum number of states in a
hypothetical finite automaton that recognizes the language.
 Step 3: Divide the string W into three substrings X, Y, and Z

We need to split the string 'W' into three parts, namely 'X', 'Y', and 'Z'. The important condition here is that the
length of the substring 'Y' should be greater than zero. So that 'Y' must contain at least one symbol. We also
need to make sure that the combined length of 'X' and 'Y' is less than or equal to the constant 'C'.

Step 4: Pump the substring Y

The most important part of the pumping lemma is that we can repeat the substring 'Y' any number of times,
and the resulting string will still belong to the language. So it means that we can create new strings by taking
the original string 'W' and replacing the 'Y' substring with 'Y' repeated 'i' times, where 'i' is any non-negative
integer. The resulting string will be of the form 'XYi Z', where Y^i represents the substring 'Y' repeated 'i'
times.

Step 5: The contradiction

If, for any choice of 'W', 'X', 'Y', and 'Z' satisfying the conditions mentioned above, we can find a value of 'i'
for which the string XYi Z does not belong to the language, then our initial assumption that the language is
regular must be false.

Let us see an example that what we have covered here.

Example of Pumping Lemma for Regular Expression

Suppose we have a language, L = {an bn | n >= 1}. This language consists of strings with an equal number of
'a's and 'b's, with at least one 'a' and one 'b'. Just apply the above steps inside this.

Consider a language as regular − We start by assuming that L is a regular language.

Assume a constant C and select a string W − Let's choose the constant C = 3 and the string W = "aaa bbb" (n =
3). The length of W is 6, which is greater than C.

Divide the string W into three substrings X, Y, and Z − We can divide W into X = "aa", Y = "a", and Z = "
bbb". Notice that the length of Y is 1, which is greater than zero, and the length of X Y is 3, which is less than or
equal to C.

Pump the substring Y − Now, let's try pumping the substring Y. If we repeat Y once, we get the string "aa a
bbb" (n = 4), which is still in the language. However, if we repeat Y twice, we get the string "aa aa bbb" (n = 5),
which is not in the language.

The contradiction − Since we found a value of 'i' (i = 2) for which the string ' XY^i Z ' does not belong to the
language, our initial assumption that L is regular must be false.

If we try to make the FSM, it will be like −

This finite automaton can accept strings with an equal number of 'a's and 'b's. However, it cannot remember
the exact count of 'a's and 'b's.

When pumping the substring 'Y' (in our example, 'a'), the automaton loses track of the number of 'a's, leading
to an imbalance in the number of 'a's and 'b's, thus creating a string that doesn't belong to the language. This
demonstrates the limitation of a finite automaton and why L cannot be recognized by one.

Theorem: Let L be a regular set. Then there is a constant n such that if Z is any word in L and |Z| ≥ n we can
write z = u v w such that |u v| ≤ n, |v| ≥ 1 for all i ≥ 0, u vi w is in L. The n should not be greater than the
number of states.

Proof: If the language L is regular it is accepted by a DFA. M = (Q, Σ, δ, q0, F). With some particular number
of states say, n. Consider the input can be a1, a2, a3, .... am, m≥n. The mapping function δ could be written as
δ(q0, q1, q2, q3 ... qi) = qi

The transition diagram is as shown in Fig. 2.6.1.

If qm is in F i.e. q1, q2, q3, … qm is in L(M) then a1, a2,...aj ak+1 ak+2 ......am is also in L(M)

. Since there is path from q0 to qm that goes through qj but not around the loop labelled aj+1 .... ak. Thus

δ (q0, a1, aj ak+1 ...am) = δ (δ (q0, q1, ... qj), ak+1 .... am)

= δ (qj, qk+1 ...qm)

= δ (qk, qk+1 ...qm)

= qm

That is what we have proved that given any long string can be accepted by FA, we should be able to find a
substring near the beginning of the string that may be pumped i.e. repeated as many times as we like and
resulting string may be accepted by FA.

• Advantage of Pumping Lemma

The pumping lemma is used to check whether given language is regular or not.

Example 1 Show that the set L = { bi2 |i>1} is not regular.

ii) Prove that L = {0i2 /i is an integer; i≥1 is not regular.

Solution: We have to prove that the language L= bi2 is not regular. This language is such that number of b's is
always a perfect square.

For example, if we take i = 1

L = b12 = b the length = 12

= b22 = bbbb length = 22

and so on.

Now let us consider

L = bn2 where length = n2

it is denoted by z.

|z| = n2

By pumping lemma z = u v w

where 1 ≤ |v| ≤ n

As z = uvi w where i = 1

Now we will pump v i.e. make i = 2.

As we made i = 2 we have added one n2.

1≤ | v | ≤ n.

n2 +1 ≤ uvw | ≤ n+n2

i.e. n2 +1 ≤ | uvw | ≤ n2 +n+n+1

i.e. n2 +1 ≤ | uvw | ≤ (n+1)2

= n2 ≤ | uvw | ≤ (n+1)2

Thus the string lies between two consequetive perfect squares. But the string is not a perfect square. Hence we
can say the given language is not regular.

For example,

L = bi2

Let i = 2

L = bbbb

L = uvw

Assume uvw = bbbb

Take

u=b
v = bb

w=b

By pumping lemma, even if we pump v i.e. increase v then language should show the length as perfect square.

= uvw

= uv. vw

= bbbbbb

= length of b is not a perfect square

Thus the behaviour of the language is not regular, as after pumping something onto it does not show the same
property (being square for this example.)

Example 2 Is the following language regular ? Justify your answer

L = {02n|n≥1}

Solution: This is a language length of string is always even.

i.e.

n = 1; L = 00

n =2 L = 00 00 and so on.

Let L = uvw

L = 02n

|z| = 2n = u vi w

If we add 2n to this string length.

|z| = 4n = uv. vw

= even length of string.

Thus even after pumping 2n to the string we get the even length. So the language L is regular language.

Example 3 Show that L = {0n 1n+1 | n>0} is not regular.

Solution: Let us assume that L is a regular language.

|z| = |uvw|

= 0n 1n+1

Length of string [z] = n + n + 1 = 2n + 1.

That means length is always odd.

By pumping lemma

= |uv. vw|

That is if we add 2n + 1

2n + 1 < (2n + 1) + 2n + 1

2n+1 < 4n+ 2

But if n = 1 then we obtain 4n+ 2 = 6 which is no way odd. Hence the language becomes irregular.

Even if we add 1 to the length of |z|, then

|z| = 2n + 1 + 1

= 2n + 2

= even length of the string.

So this is not a regular language.

Example 4 Show that set L = (0i1i | i ≥ 1} is not regular.

Solution: Assume that L = {0i 1i | i ≥ 1} is regular.

Let, w = 0 1 such that |w| = 2n. By pumping lemma we can write

w = xyz such that |xy| ≤ n and |y| ≠ 0.

Now if xy1z ϵ L then the language L is said to be regular.

There are many cases - i) y has only 0's ii) y has only 1's iii) y has both 0's and 1's. i) If y has only O's then the
string

w = 0n-k|n = xz since y = 0k and i = 0

Surely n-k ≠ n. Hence xz € L.

Hence our assumption of being L regular is wrong.

ii) If y has only 1's then, for i = 0 and y = 1k

w = xz = 0n 1n-k

As n ≠ n-k, xz = w € L

Again L is not regular.

iii) If y has 0's and 1's then

w = 0n-k 0k 1j 1n-j = xyi z

If i = 2 then

w = 0n-k 02k 12j 1n-1 € L

Hence from all these 3 cases it is clear that language L is not regular.

Example 5 Which of the following languages is regular? Justify.

1) L = {an bm | n, m ≥ 1}

2) L = {an bn | n ≥ 1}

Solution : 1) Let, L = {an bm | n, m ≥ 1}

Here the number of a's and b's can be at least one. We can write the regular expression for given L as

r.e. = a+ b+

For this regular expression the FA can be

As we can draw the FA for representing given language, the given L is said to be regular.

2) Given L = {an bn | n ≥ 1} is not regular. Refer similar example 2.6.4.

Example 6 Using pumping lemma for the regular sets, prove that the language L= {ambn | m>n} is not
regular.

Solution: Let us assume that L is a regular language. The string W ϵ L such that

|W| = | xyz | = am bn

Length of string |W| = m + n, where m > n. By pumping lemma we can write

W = xyz such that |xy| ≤ n |y| ≠ 0.

Now if xyiz ϵ L then the language is said to be regular.

There are many cases: i) y has only a's

ii) y has only b's

iii) y has both a's and b's.

i) If y has only a's then assume W = a3 b2.

If we map W = xyiz with i = 0. Then W in equation (1) becomes

W= a aa bb

x=a, y=aa, z=bb

W = xz y1 = y0 = 1

W = abb = a1b2 € {L = am bn | m>n}

ii) y has only b's then assume W = a3 b2

If we map W = xyiz with i = 3 then W in equation (2) becomes

Regular Expressions and Languages

W= aaa bb

x = aaa

y=b

z=b

W = (aaa) (bbb) (b)

W = a3 b4 € {L = am bn | m > n}

iii) y has both a's and b's. Then assume W = a3 b2.

If we map W = xyiz with i = 2 then W in equation (3) becomes

W = aa ab b

x = aa

y = ab

z=b

W = (aa) (abab) (b)

= a3 bab2 € ambn

From above three cases it is clear that our assumption of L being regular is wrong. This proves that given L =
ambn is not regular.

The simple way to know whether given language is regular or not is that try to draw finite automata for it, if
you can easily draw the FA for the given L then that language is surely the regular otherwise not.

Example 7 Using pumping lemma for regular sets, prove that the language L = {0m1n 0m+n | m ≥ 1 and n ≥
1} is not regular.
Solution: Let us assume that L is a regular language. The input string w ϵ L such that

|w| = | xyz | = 0m1n 0m+n

By pumping lemma we can write

w = xyz such that |xy| ≤ n and |y| ≠ 0.

There are three cases: i) y has only 0's

ii) y has only 1's

iii) y has 0's and 1's.

Case i) y has only 0's

Consider w = 00010000

If we map w = xyz then

By pumping lemma,

w = xyiz

W = 0 00 10000

0 = x, 00 = y, 10000 = z

if i = 2 then

w = xyyz i.e.

= 0(00) (00) (10000)

W = 05 11 04 € 0m 1n 0m+n

Case ii) y has only 1's

Consider w = 00110000

If we map w = xyz then

By pumping lemma,

w = 00 11 0000

x = 00, y = 11, z = 0000

w = xyiz

if i = 2 then
w = xyyz i.e.

= 00(11) (11) (0000)

= 02 14 04 € 0m 1n 0m+n

Case iii) y has 0's and 1's

Consider w = 001000

w = 0 01 000

x = 0, y = 01, z = 000

If we map w = xyz then

By pumping lemma,

w = xyiz

If i = 2 then

w = xyyz i.e.

= 0 (01) (01) (000)

= 021 011103 € 0m1n 0m+n

From above three cases, it is clear that our assumption of L being regular is wrong. This proves that given L =
0m1n 0m+n is not regular.

Example 8 Prove that following languages are not regular:

i) { w ϵ {a,b}* |w = wR} ii) Set of strings of 0's and 1's beginning with 1, whose value treated as a binary
number is prime.

Solution: i) Let, the given language

• L = {w ϵ {a, b}* |w = wR} is regular

• Suppose there is a DFA for L with p states. Let w be word in L. We will pump the strings, such that

w = xyz.

• We will choose w = 0P10P ϵ L

• By pumping Lemma,

w = xyz, y ≥ 1,|xy|≤ p and

w = xyiz is in L for every i

• The pumping part is at the beginning of string. Hence |xy|≤ p and xy consists of 0's only

• Since |y| ≥ 1, y contains at least one 0.

• If i = 2 then w = xyyz and it must ϵ L

if w = 00 0 1000

x = 00

y=0

z = 1000

w = xyyz

w = 00001000 € L

• This shows that, our assumption of being L is regular is wrong.

• This proves that given language is not regular.

ii) L = Binary numbers of prime numbers

Let, w = xyz ϵ L we assume that L is a binary language of prime numbers.

• Assume | xyz |= n.

• Assume L is regular.

• By pumping lemma.

w = xyz, |y| ≥ 1, |xy| ≤ p and w = xyiz is in L for every i

• i = 2, then

w = xyyz

|w| = n+1 € L

This shows that our assumption of L being regular is wrong and L is non-regular.