Course Instructor

ANUJ GHIMIRE
DISCLAIMER
 This document does not claim any originality and
cannot be used as a substitute for prescribed textbooks.
 The information presented here is merely a collection
from various sources as well as freely available material
from internet and textbooks.
 The ownership of the information lies with the
respective authors or institutions.
 Regular Expression and Finite
Automata
 A language denoted by L over an alphabet ∑ is subset
of all the strings that can be formed out of ∑.
 Simply, language is subset of kleen closure over an
alphabet ∑ :L  ∑* (set of strings chosen from ∑*
defines language).
 Regular Expression is a formula for representing a
language in terms of a form combined using 3
operations union, concatenation and kleen closure.
 Regular Expression and Finite
Automata
 A regular expression is a rule that describe a whole set
of strings belongs to certain language.
 Any regular expression is recursively defined as:
 Empty state (φ), empty string(ε) symbol of input
alphabet (∑) are regular expression
 Let R1 and R₂ be regular expression then union of R1 and
R2 denoted by (R1 + R2) is also Regular Expression.
 Let R1 and R₂ be regular expression then concatenation
of R1 and R2 denoted by (R1 . R2) is also Regular
Expression.
 Let R be regular expression then kleen closure of R
denoted by R* is also Regular Expression.
 Regular Expression and Finite
Automata
 Regular expression are the language generator and
finite automata are the language acceptor.
 The regular expression approach for describing regular
language is fundamentally different from the finite
automata approach.
 However, these two notations represent exactly the
same set of languages, called regular languages.
 A language is said to be regular language if and only if a
finite automata recognizes it.
Conversion of Regular Expression To
Finite Automata
 We can convert the finite automata to its equivalent
regular expression and vice versa.
 We have already discussed that DFA and two kinds of
NFA with & without ε-transition which accept the
same class of languages.
 In order to show that the regular expressions define
the same class, we must show that:
 Every language defined by one of these automata is also
defined by a regular expression. For this proof, we can
assume the language is accepted by some DFA.
Conversion of Regular Expression To
Finite Automata
 Every language defined by a regular expression is
defined by one of these automata. For this part of proof,
the easiest is to show that there is an NFA with ε-
transitions accepting the same language.

ε-NFA NFA

RE DFA

Fig: Plan for showing the equivalence of four different notations for regular language.
Conversion of Regular Expression To
Finite Automata
 For the conversion of regular expression to finite
automata we have some important basic rules as
follows:
 When we have the expression like (a+b) or (a  b) or
(a|b)
a

q0 a, b q1
q0 q1 OR

b
Conversion of Regular Expression To
Finite Automata
 When we have the expression of the form a.b then

a b
q0 q1 q2

 If we have the expression of the form a* then:

a
q0

 If we have the expression of the form a+ then:

q1 a q2 a
Conversion of Regular Expression To
Finite Automata_Example
 Convert the given RE into FA:
 ba*b
a

b b
q0 q1 q2

 (a+b)c
a

q0 q1 c q2

b
Conversion of Regular Expression To
Finite Automata_Example_1
 Convert the given RE into FA:
 (a|b)*(abb|a+ b)
To solve this problem we first break down the given RE,
construct the respective FA and then combine them.
for (a|b)*
a, b
q0

for abb
a b b
q1 q2 q3 q4
Conversion of Regular Expression To
Finite Automata_Example_1
for a+ b a

a b
q4 q5 q6

Now we combine all of them into the single FA as:

a, b a

a b
q0 q4 q5

a
b b
q1 q2 q3
Conversion of Regular Expression To
Finite Automata_Example_2
Convert following Regular Expression to NFA and then
to DFA
L:b(baa  aba)*

 To convert the given RE into the required FA we perform

the step wise transition of the state for a particular input.
 The final FA will accept all the set of string generated by
the given RE.
 So, we draw the FA step by step which will accept all the
string that belongs to that language.
Conversion of Regular Expression To
Finite Automata_Example_2
Here, L:b(baa  aba)*
We know the FA being constructed will moves to final state
after consuming b(baa  aba)*
b(baa aba)*
q0 qf

We first transit the automata for b and then (baa  aba)*

which will take the automata to final state.
baa aba

q0 b qf
Conversion of Regular Expression To
Finite Automata_Example_2
Now to break down the input (baa  aba)* as follows:
baa

q0 b qf
aba

Again we further break down the input baa as:

a

b a
q0 b qf q1 q0

aba
Conversion of Regular Expression To
Finite Automata_Example_2
Again we further break down the input aba as:

b a
q0 b qf q1 q2

a
b
q3

There is no other input that needs to be further broken

down so this is the required FA for the given language.
Finally convert this NFA to its equivalent DFA
Conversion of Regular Expression To
Finite Automata_Example_3
Construct a NFA for the language
L: (ab*a  b*aa)

q0 a q1 a
q2

b a
b

q3 a q4

b
Conversion of Regular Expression To
Finite Automata_Example_4
Design a Deterministic Finite Automata (DFA) for the
RE:(a(ab)*b)*
q4 a,b
b
a

q0 a q1 a
q2
b
a b

q3
Required DFA b
Conversion of Regular Expression To
ε-NFA
 For the conversion of the regular expression to its
equivalent ε-NFA, we have some important basic rules
as we used before (including now ε) which is as
follows:
 When we have the expression like a*
ε

ε a ε
q0 q1 q2 q3

ε
Conversion of Regular Expression To
ε-NFA
 When we have the expression like a+
ε

ε a ε
q0 q1 q2 q3

 When we have the expression like (a.b)

ε a ε ε
q0 q1 q2 b q4
q3 q5
Conversion of Regular Expression To
ε-NFA
 When we have the expression like (a+b) or (a  b) or
(a|b)
a
q1 q3 ε
ε

q0 q5

ε
q2 b q4 ε
Conversion of Regular Expression To
ε-NFA_Example_1
 Convert the given regular expression into ε-NFA
RE: (a+b)*
Solution,
Let us think (a+b)* whole as a* then draw the ε-NFA as per
the rule of a* as:
ε

ε a ε
q0 q1 q2 q3

ε
Conversion of Regular Expression To
ε-NFA_Example_1
Now substitute a+b 2nd diagram in place of a in 1st diagram as

a
q1 q3 ε
ε

q0 q5

ε
q2 b q4 ε
Conversion of Regular Expression To
ε-NFA_Example_1
But we have (a+b) instead of a so, a+b form can be
formed from the rule of ε as:
ε

a
q1 q3
ε
ε
ε q0 q5 ε qf
qs

ε ε
q2 b q4
This is the required
ε-NFA of (a+b)* ε
Conversion of Regular Expression To
ε-NFA_Example_2
 Convert the given regular expression into ε-NFA
RE: (00+11)*
Solution,
Let us think (00+11)* whole as a* then draw the ε-NFA as per
the rule of a* as:
ε

ε a ε
q0 q1 q2 q3

ε
Conversion of Regular Expression To
ε-NFA_Example_2
Now substitute 00+11 in place of a in 1st diagram as

00
q1 q3 ε
ε

q0 q5

ε
q2 11 q4 ε
Conversion of Regular Expression To
ε-NFA_Example_2
But instead of a we have 00+11. Again two inputs 00 and 11
cannot remain at same place in diagram so we subdivide 00
and 11 and draw for each separately as follows;
for 00 and 11
ε 0 ε ε
q0 q1 q3 0 q7
q5 q9

ε 1 ε ε
q0 q2 q4 1 q8
q6 q9
Conversion of Regular Expression To
ε-NFA_Example_2
Again 00 and 11 can be converted in ε-NFA as:

0 ε 0 q7
q1 q3 q5
ε ε

q0 q9

ε ε
q2 1 ε 1 q8
q4 q6
Conversion of Regular Expression To
ε-NFA_Example_2
Now finally its closure is drawn as:
ε

0 ε q5 0 q7
q1 q3
ε ε
qs ε q0 q9 ε qf
ε 1 ε 1 ε
q2 q4 q6 q8

ε
This is the required
ε-NFA of (00+11)*
 Conversion of FA to Regular
Expression
 We use Arden’s Theorem to convert the FA to RE.
 Let P and Q be the two regular expression such that P
does not contain the empty string (ε) then regular
expression R of the form R=Q+RP has the unique
solution as:
R=QP*
 Conversion of FA to Regular
Expression
 Find RE for the given DFA
b
q1 q2

a b a

q3 q4 a, b

b
 Conversion of FA to Regular
Expression
Here the equation for each in terms of incoming
transitions are:
q1=ε+q2b+q3a-----------(i) {incoming coming from no where so ε}
q2=q1a-------------------(ii)
q3=q1b-------------------(iii)
q4=q2a+q3b+q4a+q4b----(iv)
 Conversion of FA to Regular
Expression
Taking equation (i) since it is final state
q1=ε+q2b+q3a-----------(i)
Substituting value of q2 andq3 from (ii) and (iii)
q1=ε+q1ab+q1ba
q1=ε+q1(ab+ba)---------(v)
Equation (v) is of the form R=Q+RP, so we can write it in
the form R=QP* according to Arden’s Theorem.
i.e. q1=ε(ab+ba)*
q1=(ab+ba)*, [according to algebraic laws of
regular expression ε.R=R]
 Conversion of FA to Regular
Expression
Since q1 is the final state and we have derived the
equation of q1 hence q1=(ab+ba)* is the required regular
expression.
so required RE=(ab+ba)*
 Conversion of FA to Regular
Expression
Obtain the RE for the given FA
a
a a

b b b q4
q1 q2 q3

a
 Conversion of FA to Regular
Expression
Here the equation for each in terms of incoming
transitions are:
q1=ε+q1a+q2a+q3a-----------(i)
q2=q1b-------------------(ii)
q3=q2b-------------------(iii)
q4=q3b+q4a+q4b----(iv)
 Conversion of FA to Regular
Expression
Taking equation (i) since q1 it is final state
q1= ε+q1a+q2a+q3a
Substituting value of q2 andq3 from (ii) and (iii)
q1= ε+q1a+q1ba+q2ba
q1= ε+q1a+q1ba+q1bba
q1=ε+q1(a+ba+bba)---------(v)
Equation (v) is of the form R=Q+RP, so we can write it in the
form R=QP* according to Arden’s Theorem.
i.e. q1=ε(a+ba+bba)*
q1=(a+ba+bba)*, [according to algebraic laws of regular
expression ε.R=R]
 Conversion of FA to Regular
Expression
Taking equation (ii) since q2 is also final state
q2=q1b
q2=(a+ba+bba)*b
Taking equation (iii) since q3 is also final state
q3=q2b
q3=(a+ba+bba)*bb
We have derived the expression for all the final states so
the regular expression is union of all the obtained expression
i.e.
q1  q 2  q3
RE=(a+ba+bba)*  (a+ba+bba)*b  (a+ba+bba)*bb
 Conversion of FA to Regular
Expression
Find RE for given DFA

a
b
b a b q4
q1 q2 q3

b
 Closure Properties of Regular
Language
 Closure refers to some operation on a language, resulting in
a new language that is of the same “type” as originally
operated on i.e. regular.
 Those operations on regular languages that are certain to
result in regular language are known as closure qualities.
 The class of language accepted by finite automata is closed
under:
 Union
 Concatenation
 Kleen Closure
 Complement
 Intersection
 Closure Properties of Regular
Language (Union)
 Let R1 and R2 are the regular language then the union
of R1 and R2 denoted by R1+R2 or R1  R2 is also
regular.
 To show that R1+R2 are regular language we need to
design a non deterministic automata which can
recognize the language (R1+R2).
 For this let us consider the non deterministic automata
M1 which can recognize R1 i.e. string generated by R1
will be accepted by M1.
 M1 can be defined as M1= (Q1, ∑1, δ1, q1 , F1) such
that R1=L(M1)
 Closure Properties of Regular
Language (Union)
 Also consider another non deterministic automata M2
which can recognize R2 i.e. string generated by R2 will
be accepted by M2.
 M2 can be defined as: M2= (Q2, ∑2, δ2, q2 , F2) such
that R2=L(M2)
 We now construct a non deterministic automata such
that L(M)=L(M1)+L(M2).
 Closure Properties of Regular
Language (Union)
A simple non deterministic automata can be
constructed easily as:

q1 qi qf q2 qh qs

M1 M2

ε
q2 qh qs
q0
ε q1 qi qf
M
 Closure Properties of Regular
Language (Union)
 Simply newly constructed automata M uses non-
determinism to guess whether input is in L(M1) or in
L(M2).
 The automata M then processes the string exactly as
the corresponding automata either M1 or M2 so it
follows L(M)=L(M1)+L(M2).
 The formal proof can be given as:
From these two NFAs, we will construct an NFA
M = (Q, ∑, δ, q0, F), such that L(M) = L(M1) + L(M2)
 Closure Properties of Regular
Language (Union)
 Different tuple of M can be defined as:
Q: Q1  Q2  q0
∑ : ∑1  ∑2  {ε}
q0 : q0
F: Set of Final States (F  Q)
δ : δ1  δ2  δ (q0,ε) → q1  δ (q0,ε) → q2
 Closure Properties of Regular
Language (Union)
 That is M beings any computation by non
deterministically choosing to enter either initial sate of
M1, or the initial state of M₂.
 M then reproduces either M1, or M2, thereafter.
 Hence M accepts the string w if and only if M1, accepts w
or M2 accepts w and L(M)=L(M1)+L(M2).
 Hence, regular properties are closed under union.
 Steps in Union of R1 and R2
 Create a new start state.
 Make a ε-transition from the new start state to each of
the original start states.
 Closure Properties of Regular
Language (Concatenation)
 Let R1 and R2 are the regular language then the
concatenation of R1 and R2 denoted by R1.R2 is also
regular.
 To show that R1.R2 are regular language we need to
design a non deterministic automata which can
recognize the language (R1.R2).
 For this let us consider the non deterministic automata
M1 which can recognize R1 i.e. string generated by R1
will be accepted by M1.
 M1 can be defined as M1= (Q1, ∑1, δ1, q1 , F1) such
that R1=L(M1)
 Closure Properties of Regular
Language (Concatenation)
 Also consider another non deterministic automata M2
which can recognize R2 i.e. string generated by R2 will
be accepted by M2.
 M2 can be defined as: M2= (Q2, ∑2, δ2, q2 , F2) such
that R2=L(M2)
 We now construct a non deterministic automata such
that L(M)=L(M1).L(M2).
 Closure Properties of Regular
Language (Concatenation)
A simple non deterministic automata can be
constructed easily as:

q1 qi qf

q2 qh qs
qa
M2

qb

M1
 Closure Properties of Regular
 z
Language (Concatenation)

q1 qi qf ε

qa q2 qh qs
ε

ε
qb

M
 Closure Properties of Regular
Language (Concatenation)
 Simply newly constructed automata M starts from M1,
after consuming all the string generated by R1 it
reaches to the one of the final states of M1.
 Then using non-determinism the automata reaches to
the starting state of M2.
 The automata M then processes the string exactly as
the corresponding automata of M2 making
L(M)=L(M1).L(M2).
 The formal proof can be given as:
From these two NFAs, we will construct an NFA
M = (Q, ∑, δ, q0, F), such that L(M) = L(M1).L(M2)
 Closure Properties of Regular
Language (Concatenation)
 Different tuple of M can be defined as:
Q: Q1  Q2
∑ : ∑1  ∑2  {ε }
q0: q1
F: Set of Final States (F  Q2)
δ : δ1  δ2  δ (qf, ε) → q2 where qf Є F1
 That is M beings from starting state of M1 and transits
according to transition function of M1 until it reaches
the final state of M1.
 Closure Properties of Regular
Language (Concatenation)
 Then from any of the final state of M1 the automata by
non determinism enters to the initial state of M₂.
 M then reproduces M2, thereafter.
 Hence M accepts the string w if and only if M2
accepts w and L(M)=L(M1).L(M2).
 Hence, regular properties are closed under
concatenation.
 Steps in Concatenation of R1 and R2
 Put a ε-transition from each final state of M1 to the
initial state of M2.
 Make the original final states of M1 as non final.
 Closure Properties of Regular
Language (Kleen Closure)
 Let R1 be the regular language then the kleen closure
of R1 denoted by R1* also regular.
 To show that R1* is regular language we need to design
a non deterministic automata which can recognize the
language R1*.
 For this let us consider the non deterministic automata
M1 which can recognize R1 i.e. string generated by R1
will be accepted by M1.
 M1 can be defined as M1= (Q1, ∑1, δ1, q1 , F1) such
that R1=L(M1)
 Closure Properties of Regular
Language (Kleen Closure)
 We now construct a non deterministic automata such
that L(M)=R1*.

q1 q2 qf

qa

qb

M1
 Closure Properties of Regular
 a
Language (Kleen Closure)
ε
ε

qs ε q1 q2 qf

qa ε qr
ε

ε qb ε

M
 Closure Properties of Regular
Language (Kleen Closure)
 Simply newly constructed automata M begins from new
starting state (which is also the final state as it may accept ε
string) and uses non-determinism to reach the starting
state of M1.
 The automata M then processes the string exactly as the
corresponding automata of M1.
 For the repetition of the string the automata uses the non-
determinism from any of the final state of M1 to the initial
state of M1 making L(M)=R1*.
 The automata finally uses non-determinism to reach any of
the final state of M from the original final state of M1.
 Closure Properties of Regular
Language (Kleen Closure)
 The formal proof can be given as:
From the original NFA, we will construct new NFA
M = (Q, ∑, δ, q0, F), such that L(M) = R1*
 Different tuple of M can be defined as:
Q: Q1  {qs}  {qr}
∑: ∑1  {ε}
q0: qs
F: {qs ,qr}
δ : δ1  δ (qi, ε) → q1  δ (qs, ε) → q1 where qi Є F1
 Closure Properties of Regular
Language (Kleen Closure)
 Steps in Kleene Closure of R1
 Make a new start state (which is also the final state as it
may accept ε string); connect it to the original start state
with a ε-transition.
 Make a new final state; connect the original final state
(which becomes non final) to it with ε -transitions.
 For the repetition of the string use the ε -transitions
from any of the final state of M1 to the original initial
state i.e. of M1.
 Closure Properties of Regular
Language (Complement)
 Let R1 be the regular language then the complement of
R1 denoted by 𝑅1 also regular.
 To show that 𝑅1 is regular language we need to design a
non deterministic automata which can recognize the
language 𝑅1 .
 For this let us consider the non deterministic automata
M1 which can recognize 𝑅1 i.e. string generated by 𝑅1
will be accepted by M1.
 M1 can be defined as M1= (Q1, ∑1, δ1, q1 , F1) such
that 𝑅1 =L(M1)
 Closure Properties of Regular
Language (Complement)
 We now construct a non deterministic automata such
that L(M)=𝑅1 .

q1 qi qf q1 qi qf

qa qa

qb qb

M1 M
 Closure Properties of Regular
Language (Complement)
 The formal proof can be given as:
From the original NFA, we will construct new NFA
M = (Q, ∑, δ, q0, F), such that L(M) = 𝑅1
 Different tuple of M can be defined as:
Q: Q1
∑: ∑1
q0: q1
F: {Q-F1}
δ : δ1
 Closure Properties of Regular
Language (Complement)
 Steps in Complement of R1
 Make the non final states of original automata as a final state
and vice versa.
 Intersection Properties of Regular Language
R1  𝑹𝟐=𝑹𝟏 +𝑹𝟐 using De-Morgan’s Law
 If R1 and R2 is regular then 𝑅1 and 𝑅2 are also regular using
complement properties.
 If 𝑅1 and 𝑅2 are regular then 𝑅1 +𝑅2 is also regular by union
properties.
 𝑅1 +𝑅2 is regular then its complement 𝑅1 +𝑅2 is also regular
from complement properties.
 𝑅1 +𝑅2 is equivalent to R1  𝑅2 so, R1  𝑅2 is also regular.
Pumping Lemma
 We have concluded that the class of regular languages
is closed under various operations, and these
languages can be described by (deterministic or
nondeterministic) finite automata and regular
expressions.
 These properties helped in developing techniques for
showing that a language is regular.
 Now, we will discuss about the tool that can be used to
prove that certain languages are not regular.
Pumping Lemma
 For the regular language
 The amount of memory that is needed to determine
whether or not a given string is in the language is finite
and independent of the length of the string.
 If the language consists of an infinite number of strings,
then this language should contain infinite subsets
having a fairly repetitive structure.
 Automatically, languages that do not follow above
criteria should be non-regular.
Pumping Lemma
 Consider the language L: {0n 12n : n ≥ 0}.
 We can prove this language to be non regular, since DFA
has the limited memory and it seems unlikely that a
DFA can remember how many 0’s it has seen when it has
reached the border between the 0’s and the 1’s.
 Thus we cannot generate the number of 1 exactly two
times the number of 0.
 Consider another language L:{0n : n is a prime }
 The given language is also not regular because the prime
numbers do not seems to have any repetitive structure
that can be used by a DFA
Pumping Lemma
 These ideas are accurate but not sufficiently precise to
be used in formal proofs.
 We will establish a property that all regular languages
must possess called the Pumping Lemma.
 If a language does not have this property, then it must
be non regular.
 The pumping lemma states that any sufficiently long
string in a regular language can be pumped, i.e., there
is a section in that string that can be repeated any
number of times, so that the resulting strings are all in
the language.
 Pumping Lemma for Regular
Language
 Theorem: Let L be a regular language. Then there
exists an integer p ≥ 1 and p ≥ m(no. of state of FA),
called the pumping length, such that any string w in L,
with |w| ≥ n, can be decomposed into three parts as
w = xyz, such that:
 |y|≥ 1, y∉ ε
 |xy|≤ p
 for all i ≥ 0, xyi z ∈ L
 In words, the pumping lemma states that by replacing
the portion y in w by zero or more copies of it, the
resulting string is still in the language L.
 Pumping Lemma for Regular
Language
 Note
 If any language pass the Pumping Lemma Test
then it is undecidable that the language is
regular or not.
 But, if any language fails the Pumping Lemma
Test then the language is obvious not regular.
 Pumping Lemma for Regular
Language
Proof:
Let L be a regular language and w Є L.
Let w = a1a2a3…………..an and the set of states are q1, q2,
q3…………..qm.
From the theorem of pumping lemma w can be
decomposed into three parts as w=xyz
Now its finite automata will be as follows:
x y z q4
q1 q2 q3
 Pumping Lemma for Regular
Language
Here, |w| = 3, but total states are 4. By pigeon hole
principle, any of the two states of FA must coincide.
According to our requirement state q2 & q3 gets coincide.
y

q1 x q2=q3 z q4

Now in general form,

w = a1a2a3………….……..an can be decomposed as:
x= a1a2a3…………..ai
y= ai+1ai+2ai+3…………..aj
z= aj+1aj+2aj+3…………..an
 Pumping Lemma for Regular
Language
So automata becomes y= ai+1ai+2ai+3…………..aj

q1 qi=qj q4
x =a1a2a3…………..ai z= aj+1aj+2aj+3…..an

Now we have to show that xyi z ∈ L for i ≥ 0

When i=0, we get w=xz which is processed by FA.
When i=1, we get w=xyz, which is also accepted by FA.
Similarly, FA processes the strings for all the values of i. So,
we say that xyi z ∈ L all i ≥ 0.
Hence proved.
 Pumping Lemma for Regular
Language
 To prove the language L is not Regular using Pumping
Lemma make following steps (prove by contradiction):
 Assume that L is regular.
 It has to have a pumping length (say p)
 All strings longer than p can be pumped |w| ≥ p
 Now find a string ‘w' in L such that |w| ≥ p and divide w
into three parts xyz considering all possible ways such
that:
 Pumping Lemma for Regular
Language
 |y|≥ 1, y∉ ε
 |xy|≤ p
 Show that xyi z Є L for some i
 Try to conclude that none can satisfy all the 3 pumping
conditions at the same time.
 w cannot be Pumped  CONTRADICTION.
 Pumping Lemma for Regular
Language_Example_1
Show that the language L: {0n1n : for n ≥ 0} is not regular.
Solution,
We use the method of proof by contradiction to make the
proof. So consider L: {0n 1n : for n ≥ 0} is regular.
Also, it has a pumping length of p.
So, w= 0p1p
We now divide w into three parts xyz as:
x=oq
y=or r>0
z=op-(q+r)1p
 Pumping Lemma for Regular
Language_Example_1
for pumping factor i=2,
xy2 z = oq(or)2op-(q+r)1p
= oqo2rop-(q+r)1p
= oq+2r+p-q-r1p
= op+r1p
Since r >0, p+r > p
Therefore ap+r bp is not of the form apbp i.e. xy2z ∉ L
Hence the given language is not regular by pumping
lemma.
 Pumping Lemma for Regular
Language_Example_2
Show that the language L: {anban : for n ≥ 0} is not
regular.
Solution,
We use the method of proof by contradiction to make the
proof. So consider L: {anban : for n ≥ 0} is regular.
Also, it has a pumping length of p.
So, w= apbap
Let p=5
w= a5ba5
w=aaaaabaaaaa
 Pumping Lemma for Regular
Language_Example_2
Dividing w into x, y and z we get,
Case-I: When 'y' contains only ‘aa'
w = aa aa abaaaaa [x=aa, y=aa, z=abaaaaa]
Checking for case-I
Let, i=2
w =xy2z
w = aa aaaa abaaaaa
w = a7ba5 ∉ L
So, case-I fails as the power of a's at the start and end of the
string are not equal.
 Pumping Lemma for Regular
Language_Example_2
Case-II: When 'y' contains 'aaa‘
w = aa aaa baaaaa [x=aa, y=aaa, z=baaaaa]
Let, i=2
w =xy2z
w = aa aaaaaa baaaaa
w = aaaaaaaabaaaaa ∉ L
So, case-II fails as it doesn’t follow the pattern anban.
Hence, on pumping i.e. xyi z none of the case follow all the
three conditions of regular language. So, the given language
L: {anban : for n ≥ 0} is not regular.
 Pumping Lemma for Regular
Language_Example_3
Show that the language L: {anb2n: for n ≥ 0} is not regular.