Regular Expression

Regular expressions
 The language accepted by DFA or NFA and ε-NFA is called regular
language.
 A regular language can be described using regular expressions
consisting of the symbols such as alphabet in Σ, the operators such as
‘.’, ’+’ and ‘*’.
 The three operators used to obtain a regular expression are:
+ :union operator (least precedence)
. : concatenation operator (next least precedence)
* : closure operator (highest precedence)
 Regular expression
 Definition: A regular expression is recursively defined as
follows.
1.ϕ is a regular expression denoting an empty language.
2. ε-(epsilon) is a regular expression indicates the language containing an
empty string.
3. a is a regular expression which indicates the language containing only
{a}
4. If R is a regular expression denoting the language LR and S is a regular
expression denoting the language LS, then
a. R+S is a regular expression corresponding to the language
LRULS.
b. R.S is a regular expression corresponding to the language LR.LS..
c. R* is a regular expression corresponding to the language LR*.
5. The expressions obtained by applying any of the rules from 1-4 are
regular expressions.
• L={Ɛ,a,b,aa,ab,ba,bb,aaa,bbb,aba,abb,bba,}
• L={abb, aabb,ababbababb, aaaaaabb,}
• L={aa,aabab,bbbbaab, bababaabaabb,}
• L={Ɛ,a,b,c,ab,ac,bc,aaaabc,bbbb,cccc,bc,}
• L={a,bb,ababa,abbabbabb,}
The table shows examples of regular expressions and the language corresponding to
these regular expressions.

Regular
Meaning
expressions

Set of strings of a’s and b’s of any length including the NULL
(a+b)*
string.

(a+b)*abb Set of strings of a’s and b’s ending with the string abb

ab(a+b)* Set of strings of a’s and b’s starting with the string ab.

(a+b)*aa(a+b)* Set of strings of a’s and b’s having a sub string aa.

Set of string consisting of any number of a’s(may be empty

a*b*c* string also) followed by any number of b’s(may include empty
string) followed by any number of c’s(may include empty string).
Set of string consisting of at least one ‘a’ followed by string
a⁺b⁺c⁺ consisting of at least one ‘b’ followed by string consisting of at
least one ‘c’.
Set of string consisting of at least one ‘a’ followed by string
aa*bb*cc* consisting of at least one ‘b’ followed by string consisting of at
least one ‘c’.
(a+b)* (a + bb) Set of strings of a’s and b’s ending with either a or bb

(aa)*(bb)*b Set of strings consisting of even number of a’s followed by odd number of b’s

(0+1)*000 Set of strings of 0’s and 1’s ending with three consecutive zeros(or ending with 000)

(11)* Set consisting of even number of 1’s

Problems
 Obtain a regular expression representing strings of a’s and b’s
1. having length 2.
2. Length<=2.
3. Length<=10.
4. Even length.
5. Odd length.
6. Alternate a’s and b’s.
7. At most one pair of consecutive 0’s.
8. Containing at least one a and atleast one b where Σ={a,b}
9. At least three consecutive 0’s.
10. Ending with b and has no substring aa.
11. No two consecutive zero’s
12. Second symbol from the right end is a.
13. Third symbol from right is a and fourth symbol from the right is b.
Problem
 Obtain a regular expression representing strings of a’s and b’s
14. Two or more letters but beginning and ending with the same letter where Σ={a,b}.
15. Length is either even or multiple of 3 or both.
16. Block of 4 consecutive symbols contains atleast two a’s
17. L={an bm | m+n is even}
18. L={an bm | m ≥ 1, n ≥ 1, nm ≥ 3}
19. L={an bm | n ≥ 4, m ≤ 3}
20.L={a2n b2m | m ≥ 0, n ≥ 0}
21. Not containing more that three a’s.
22. L={w: na(w) mod 3 =0 | w Є (a,b)*}
23. Do not end with 01.
24. L = {vuv : u, v Є {a,b}* and |v|=2}
25. L={w: string ends with ab or ba where w Є (a,b)* }
4. Even length.
1. Having length 2.
L={Ɛ, aa, ab, ba, bb, abab, aabb, baab……}
L={aa, ab, ba, bb}
R.E= (aa+ab+ba+bb)*
R.E=(aa+ab+ba+bb) = ((a+b)(a+b))*
=a(a+b)+b(a+b)
=(a+b)(a+b)
=(a+b)2
5. Odd length.
2. Length<=2. L={a,b,aaa, abb, ababa, aabbbaa……}
L={Ɛ, a, b, aa, ab, ba, bb}
R.E= (aa+ab+ba+bb)*(a+b)
R.E = (Ɛ+a+b+aa+ab+ba+bb) = ((a+b)(a+b))*(a+b)
= (Ɛ+ a+b)(Ɛ+ a+b) OR
= (Ɛ+ a+b)2 R.E= (a+b)(aa+ab+ba+bb)*
= (a+b)((a+b)(a+b))*
3. Length<=10.
R.E= (Ɛ+ a+b)10
6. Alternate a’s and b’s.
L={Ɛ,a,b,ab,ba,aba,bab,abab,….}

R.E=(Ɛ+b)(ab)*(Ɛ+a)

7. At most one pair of consecutive 0’s.

i.e., any num. of 1’s with no 0’s or one ‘0’ or ‘00’
case 1: 1*
case 2: (1+01)* 0 (1+01)*
case 3: (1+01)* 00 (1+10)*

R.E= 1*+ (1+01)* 0 (1+01)*+ (1+01)* 00 (1+10)*

8. Containing at least one a and at least one b
L={ab, ba, aab, bab, bbbabbb,…..}
R.E=(a+b)*a (a+b)* b (a+b)*
R.E=(a+b)*(ab+ba)(a+b)*

9. At least three consecutive a’s.

L={aaa, baaab, aaaabb, bbaaaaa, baaab,…..}
R.E= (a+b)* aaa (a+b)*

10. Ending with b and has no substring aa.

L={b, bababab, abbbbab,bbabbab,……}
R.E=(b+ab)(b+ab)*

11. No two consecutive a’s

L={a,b, bababa, bbbbba,…….}
R.E=(b+ab)*(a+Ɛ)
12. Second symbol from the right end is a.
L={ab, aabbaa, aab, bab,……..}
R.E=(a+b)*a(a+b)

13. Third symbol from right is ‘a’ and fourth symbol from the right is ‘b’.
L={abaaa, bbabb,aaabaaa,…….}
R.E=(a+b)*ba(a+b)(a+b)

14. Two or more letters but beginning and ending with the same letter where
Σ={a,b}.
L={abbbba, baaaab, abababa, bbbb, aaaa,……}
R.E=a(a+b)*a+b(a+b)*b
15. Length is either even or multiple of 3 or both.
L={Ɛ, ab,aa,abab,aba, abbabb, abbbabaaabbb,……}
R.E= ((a+b)(a+b))* + ((a+b) (a+b) (a+b))*

16. Block of 4 consecutive symbols contains atleast two a’s

L= {aabb, abab, abba, bbaa, baab, aaaa,……}
R.E=(aa(a+b)(a+b) + a(a+b)a(a+b) + a(a+b)(a+b)a + (a+b)(a+b)aa) +

17. L={a2n b2m | m ≥ 0, n ≥ 0}

L={Ɛ, aabb, aaaabbbb, aaaaaabbbbbb,…….}
R.E= (aa)*(bb)*
18. L={an bm | m+n is even}
In the following two cases m+n becomes even
Case 1: even num a’s followed by even num of b’s R.E=(aa)*(bb)*
Case 2: odd num a’s followed by odd num of b’s R.E=a(aa)*b(bb)*
R.E==(aa)*(bb)* + a(aa)*b(bb)*

19. L={an bm | n ≥ 4, m ≤ 3}

i. an where n ≥ 4 means atleast 4 a’s R.E= aaaa(a)*

ii. bm where m ≤ 3 means atmost 3 b’s R.E= (Ɛ+b+bb+bbb)

R.E= aaaa(a)* (Ɛ+b+bb+bbb)

20. L={an bm | m ≥ 1, n ≥ 1, nm ≥ 3}

i. nm≥ 3, if m=1 then n ≥ 3 R.E= aaa(a)*b

ii. nm≥ 3, if n=1 then m ≥ 3 R.E= abbb(b)*
iii. nm≥ 3, if n ≥ 2then m ≥ 2 R.E= aa(a)*bb(b)*

R.E= aaa(a)*b + abbb(b)* + aa(a)*bb(b)*

21. Not containing more that three a’s.

R.E= b* (Ɛ+a) b* (Ɛ+a) b* (Ɛ+a) b*

22. L={w: na(w) mod 3 =0 | w Є (a,b)*}

R.E= (aaa)* --- multiples of 3
R.E= (b* a b* a b* a b* )*
23. Do not end with ab.
R.E= (a+b)*(aa+ab+bb)
24. L = {vuv : u, v Є {a,b}* and |v|=2}
R.E= aa(a+b)*aa + ab(a+b)*ab + ba(a+b)*ba + bb(a+b)*bb
25. L={w: string ends with ab or ba where w Є (a,b)* }
R.E= (a+b)*(ab+ba)
26. Odd number of b’s
R.E= a* b a* (ba*ba*)*
27. The language of C identifiers
C identifiers are letters(l)- a+b+c+…..+z+A+B+……+Z
digits(d)- 0+1+2+……….+9
underscore(_)- _ and always start with l or _
R.E= (l+_)(l+d+_)*
Finite Automata and Regular
Expression
Converting R.E to Automata
• Theorem:
• Every language defined by a regular expression is also defined by a Finite Automata.
OR
• Let R be a regular expression. Then there exists a finite automaton M=(Q, ∑, δ, q0, F)
which accepts L(R).
OR
• Prove that there exists a finite automaton to accept the language L(R) corresponding to
the regular expression R.
• Proof:
• Basic: By definition, ϕ, ε and a are regular expression.

Figure: Ɛ-NFA to accept ϕ, ε and a

• The schematic representation of a regular expression R to accept the language L(R) is

shown in below figure, where q is the start state and f is the final state of a machine M.

Figure: schematic representation of FA accepting L(R)

• Induction:

• By the definition, if R1 and R2 are regular expression, the R1 + R2 , R1 . R2 , R*

are regular expression.
• Let M1=(Q1, ∑1, δ1, q1, f1) be a machine which accepts the language L(R1)
corresponding to the regular expression R1
• Let M2=(Q2, ∑2, δ2, q2, f2) be a machine which accepts the language L(R2)
corresponding to the regular expression R2
• Case 1:
• R= R1 + R2
• Construct automaton which accepts the language L(R1) or L(R2) which can
be represented as L(R1 + R2) as shown in figure

Figure: To accept the language L(R1 + R2)

• Case 2:
• R=R1 . R2
• Construct automaton which accepts the language L(R1) followed by L(R2)
which can be represented as L(R1 . R2) as shown in figure

Figure: To accept the language L(R1 . R2)

• Case 3:
• R=(R1)*
• Construct automaton which accepts the language L((R1)*) as shown in figure

Figure: To accept the language L((R1)*)

Problems
• Obtain an NFA which accepts strings of a’s and b’s starting with ab
• R.E=ab(a+b)*

Starting with ab (a+b)*

Figure: To accept language ab(a+b)*
Problems
• Obtain an NFA which accepts strings of a’s and b’s having
R.E=a*+b*+c*
Figure: To accept R.E=a*+b*+c*
Converting Finite Automata to R.E (State
elimination method)

R.E= r1*r2 (r4 + r3 r1*r2)*

• Obtain the R.E for the finite automata given below using state
elimination method.
R.E=(01+10)*
Obtain the R.E for the finite automata given
below using state elimination method.

R.E=0*+ 0*11*
=0*(Ɛ+11*)
=0*(Ɛ+1*)
=0*1*
Properties of regular
language
1. Closure properties of regular languages
⚫ Used to build recognizers for languages that are
constructed from other languages by certain operations.
⚫ Ex. Automata for intersection of two regular languages
2. Decision properties of regular languages
– Used to find whether two automata define the same
language
– Used to minimize the states of DFA
-Eg. Design of switching circuits.
closure properties of regular
languages
1. The union of two regular languages is regular.
2. The intersection of two regular languages is regular.
3. The complement of a regular language is regular.
4. The difference of two regular languages is regular.
5. The reversal of a regular language is regular.
6. The closure (star) of a regular language is regular.
7. The concatenation of regular languages is regular.
8. A homomorphism (substitution of strings for
symbols) of a regular language is regular.
9. The inverse homomorphism of a regular language
is regular
Closure of regular languages under
Boolean operations
🞆Ex1.
▪ L1={a,a3,a5,-----}
▪ L2={a2,a4,a6,-----}
▪ L1 ᴜ L2 = {a,a2,a3,a4,----}
▪ RE=a(a)*
🞆Ex2.
▪ L1={ ab,a2 b2, a3b3, a4b4,-----}
▪ L2={ab,a3 b3,a5b5,-----}
▪ L1 ᴜ L2 = {ab,a2b2, a3b3, a4b4, a5b5----}
▪ RE=ab(ab)*
Closure of regular languages under
Boolean operations
🞆Closure Under Complementation
🞆Theorem : If L is a regular language over alphabet S,
then L = Σ* - L is also a regular language.
🞆Proof: - Let L =L(A) for some DFA. A=(Q, Σ, δ, q0, F).
🞆Then L = L(B), where B is the DFA (Q, Σ, δ, q0, Q-F).
🞆That is, B is exactly like A, but the accepting states of A
have become non-accepting states of B, and vice
versa, then w is in L(B) if and only if δ*( q0, w) is in Q-F,
which occurs if and only if w is not in L(A).
🞆Ex1. L1={a,a3,a5,-----}
Σ* -L1={e,a2,a4,a6,-----}
RE=(aa)*
🞆 Ex2. Consider a DFA, A that accepts all and only the strings of 0’s
and 1’s that end in 01. i.e L(A) = (0+1)*01. The complement of L(A)
is therefore all string of 0’s and 1’s that do not end in 01
🞆Closure Under Intersection
🞆 Theorem : If L and M are regular languages, then so is L ∩ M.
🞆 Proof :Let L and M be the language of automata AL =(QL, Σ, δL, qL, FL) and
AM =(QM, Σ, δM, qM , FM).
🞆 Assume the alphabets of both automata are the same; i.e., Σ is the
union of the alphabets of L and M. AL and AM are DFA’s.
🞆 For L ∩ M, we shall construct an automata A that simulate both AL and
AM . Formally, we define
A =(QL x QM, Σ, δ, (qL , qM ) , FL xFM )
where δ ((p,q),a)=(δL (p,a), δM(q,a)).
🞆 “w” string is accepted by A if and only if both AL and AM
accept w.
i.e δL*(qL,w) ϵ FL and δM*(qM,w) ϵ FM
🞆 Thus , A accepts the intersection of L and M.
Closure of regular languages
under Boolean operations
🞆Ex1.
▪ L1={a,a2,a3,a4,a5,a6,-----}
▪ L2={a2,a4,a6,-----}
▪ L1∩L2 = {a2,a4,a6,----}
▪ RE=aa(aa)*
🞆Ex2
▪ L1={ab,a3b3,a5b5,a7b7-----}
▪ L2={a2 b2, a4b4, a6b6,-----}
▪ L1∩L2 = ϕ
▪ RE= ϕ
Closure of regular languages under
Boolean operations
🞆Ex3.
🞆 Consider a DFA that accepts all those strings that have a 0.

🞆 Consider a DFA that accepts all those strings that have a 1.

🞆The product of above two automata is given below.

Closure of regular languages
under Boolean operations
🞆The Ex3 says:
🞆This automaton accepts the intersection of the
first two languages:
🞆 Those languages that have both a 0 and a 1.
🞆Then pr represents only the initial condition, in
which we have seen neither 0 nor 1.
🞆Then state qr means that we have seen only
once 0’s, while state ps represents the condition
that we have seen only 1’s.
🞆The accepting state qs represents the condition
where we have seen both 0’s and 1’s.
🞆Ex 4
🞆Write a DFA to accept the intersection of
L1=(a+b)*a and L2=(a+b)*b that is for L1∩L2.

🞆DFA for L1 ∩ L2 = ϕ (as no string has reached to

final state (2,4))
🞆Ex5
🞆Find the DFA to accept the intersection of
L1=(a+b)*ab (a+b)* and L2=(a+b)*ba (a+b)* that
is for L1 ∩ L2
🞆Closure Under Difference
🞆Theorem : If L and M are regular languages, then
so is L – M.
🞆Proof : observe that L-M= L∩M. by theorem
closure under complement , M is regular, and by
theorem closure under intersection L∩M is
regular. Therefore L-M is regular.
🞆Ex.
▪ L1={a,a3,a5,a7,-----}
▪ L2={a2,a4,a6,-----}
▪ L1-L2 = {a,a3,a5,a7----}
▪ RE=a(a)*
Closure under Reversal
🞆 Closure under Reversal
🞆 Definition :
🞆 Reversal of a string:
🞆 The reversal of a string a1a2a3…..an is the string
written backward, i.e., anan-1……a3a2a1. Denoted by wR.
🞆 Ex: 0010R is 0100 and εR is ε.
🞆 Reversal of a language:
🞆 It is a language consisting of the reversals of all its
strings. Denoted by LR
🞆 Ex.
⚫ L={001,10,111,01}
⚫ LR={100,01,111,10}
Closure under Reversal
🞆Theorem : If L is a regular language, then LR is regular.
🞆Proof based on automata:
🞆As L is regular it can be defined by an FA, M = (Q, Σ ,
δ, q0, F), having only one final state.
🞆 If there are more than one final states, we can use ε-
transitions from the final states going to a common
final state.
🞆Let FA, MR = (QR, Σ R , δ R,q0R,FR) defines the language
LR, Where QR = Q, Σ R = Σ, q0R=F,FR=q0, and δ R (p,a)->
q, iff δ(q,a) -> p.
🞆Since MR is derivable from M, LR is also regular.
Closure under Reversal
🞆 The proof implies the following method
1. Reverse all the transitions.
2. Swap initial and final states.
3. Create a new start state p0 with transition on ε to all the accepting
states of original DFA.
🞆 Example:Let r=(a+b)* ab define a language L.
🞆 That is L = {ab, aab, bab,aaab, -----}. The FA is as given below

🞆 The FA for LR can be derived from FA for L by swapping initial and final
states and changing the direction of each edge. It is shown in the above
right figure.
Closure under Reversal
🞆Proof based on regular expression:
🞆 Let L is the language corresponding to regular expression E.
🞆 It is required to P.T there is another regular expression ER such that
L(ER)=(L(E))R .
🞆 Which is read as “language of ER is the reversal of language of E”.
🞆 Basis: By definition of R.E, we have ϕ, ε and a are R.E.
🞆 So, the reversal of regular expression ER is given by:
⚫{ε}R={ε}
⚫{ϕ}R = ϕ
⚫{a}R={a}
Closure under Reversal
🞆 Induction: Again, by definition of R.E, if E1 and E2 are regular
expressions, then: E1+E2 , E1.E2 and E1* regular expressions.
🞆 Case 1: E=E1+E2 is a R.E, then
ER=E1R+E2R
Is a R.E denoting the languages:
L(ER)=L(E1R) ᴜ L(E2R)
🞆 Case 2: E=E1.E2 is a R.E, then
ER=E1R.E2R
Is a R.E denoting the languages:
L(ER)=L(E1R).L(E2R)
🞆 Case 3: E=E1* is a R.E, then
ER=E1R
Is a R.E denoting the languages:
L(ER)=L(E1R)
Closure under Homomorphism
🞆Homomorphism:
🞆 Definition : A string homomorphism is a function on strings that works by substituting
a particular string for each symbol.
OR
🞆 Definition: Let Σ and Г are set of alphabets. The homomorphic
function
h: Σ  Г*
🞆 is called Homomorphism i.e., a substitute where a single letter is
replaced by a string. If w=a1a2a3…..an, then h(w)=h(a1)h(a2)
…….h(an).
🞆 If L is made of alphabets from Σ, then h(L)={ h(w) | w ϵ L} is called
homomorphic image.
Closure under Homomorphism
🞆 Example 1: Let Σ={0,1} , Г ={0,1,2} and h(0)=01, h(1)=112. what is h(010)? If L={00,010}.
What is homomorphic image of L?
🞆 Soln: By definition, h(w)=h(a1)h(a2)…….h(an).
So,
h(010)=h(0)h(1)h(0)
h(010)=0111201
🞆L(00,010)=L ( h(00),h(010) )
=L( h(0)h(0), h(0)h(1)h(0) )
L(00,010)=L( 0101 , 0111201 )
Closure under Homomorphism

🞆Example 2: Let Σ={0,1} , Г ={1,2,3} and

h(0)=3122, h(1)=132. what is (0+1)*(00)*?
🞆Soln: By definition, h(w)=h(a1)h(a2)…….h(an).
So,
(0+1)*(00)*=(h(0)+h(1))* (h(0)h(0))*
(0+1)*(00)*=(3122+132)*
(31223122)*
Closure under Homomorphism
🞆Theorem : If L is a regular language over alphabet Σ, and h is a
homomorphism on Σ, then homomorphic image h (L) is also regular.
🞆Proof : Let R be the regular expression and L(R) be the corresponding
regular language.
🞆We can easily find h(R) by substituting h(a) for each a in Σ .
🞆By definition of regular expression , h(R) is a regular expression and so
h(L) is regular language.
🞆So, the regular language is closed under homomorphism.
Closure under
Homomorphism
🞆 Inverse Homomorphism
🞆 Theorem : If h is a homomorphism from alphabet S to alphabet T, and L is a
regular language over T, then h-1 (L) is also a regular language.
🞆 Ex. Let L be the language of regular expression (00+1)*.
🞆 Let h be the homomorphism defined by h(a)=01 and h(b)=10. Then h -1(L) is
the language of regular expression (ba)*.
Decision properties of
regular languages
1. Is the language described empty?
2. Is a particular string w in the described language?
3. Do two descriptions of a language actually describe the same
language?
🞆This question is often called “equivalence” of languages.
Converting Among Representations
🞆Consider the time complexity of each of the conversions.
🞆Converting NFA’s to DFA’s
🞆 Time taken for either an NFA or ε-NFA to DFA can be exponential in the number of states
of the NFA.
🞆 Computing ε -Closure of n states takes O(n3) time.
🞆 Computation of DFA takes O(n3) time where number of states of DFA can be 2n.
🞆 The running time of NFA to DFA conversion including ε transition is O(n3 2n).
🞆 Therefore, the bound on the running time is O(n3s) where s is the number of states the
DFA has.
🞆 DFA to NFA Conversion
🞆 Conversion takes O(n) time for an n state DFA.
Converting Among
Representations
🞆 Automaton to Regular Expression Conversion
🞆 For DFA where n is the number of states,
🞆 Conversion takes O(n34n) by substitution method and
🞆 by state elimination method conversion takes O(n3) time.
🞆 If we convert an NFA to DFA and then convert the DFA to a
regular expression it takes the time O(n3 4n3 2n).

🞆 Regular Expression to Automaton Conversion

🞆 Regular expression to ε-NFA takes linear time – O(n) on a
regular expression of length n.
🞆 Conversion from ε -NFA to NFA takes O(n3) time.
Pumping Lemma for Regular
Languages
Applications of Pumping Lemma
• Pumping lemma is used to prove that certain languages are non-regular. But
it cannot be used to prove that a given language is regular.
• Using pumping lemma, it is possible to check whether a language accepted
by FA is finite or infinite.
• The general strategy used to prove that certain language is not regular is
shown below.
• Step 1: Assume that the language L is regular, and ‘n’ be the number of
states of FA.
• Step 2: Select the string x such that lx| ≥ n and break it into substrings u, v
and w so that x = uvw with the constraints:
v ≠ Ɛ i.e., |v| ≥1
|uv|≤n
• Step 3: Find any i such that uviw is not in L i.e., uviw ∉ L.
• According to the pumping lemma, uviw is in L for i ≥ 0. So, the result is a
contradiction to the assumption that the language is regular.
• Therefore, the given language L is not regular.
Show that L = (wwR |w ∈ (0+1)*) is
not regular.
• Step 1:
• Let L is regular and n be the number of states in FA. Consider the string:

• where n is the number of states of FA,

• w = 1....10....0 and reverse of w is given by wR=0…..01…..1 .
• Step 2: Since Ixl≥ n, we can split the string x into uvw such that |uv|≤n
• and |v| ≥1 as shown below:

• where |u| = n-1 and lv| = 1 so that |uv| = |u| + |v| = n-1+1 = n which is true.
According to the pumping lemma, uviw ∈ L for i = 0, 1, 2,...
• Step 3: According to the pumping lemma, uviw ∈ L for i = 0, 1, 2,...
• If i is 0, i.e., v does not appear and so the number of 1's on the left of x will be less
than the number of 1's on the right of x and so the string is not of the form wwR.
• So, uviw ∉ L. when i = 0.
• This is a contradiction to the assumption that the language is regular. So, the
language L = ( wwR I w e (0+11*) is not regular.
Show that L = {anbn |n≥1) is not
regular.
• Step 1:
• Let L is regular and n be the number of states in FA. Consider the string:
x =aaaabbbb.
• Since Ixl=2n≥n, we can split the string x into uvw such that |uv|≤n and |
v| ≥1 as shown below:

• where |u| = n-1 and lv| = 1 so that |uv| = |u| + |v| = n-1+1 = n which is
true.
• Step 3: According to the pumping lemma, uviw ∈ L for i = 0, 1, 2,...
• If i is 0, i.e., v does not appear and so the number of a’s will be less than
the number of b's and so the string is not of the form ‘n’ number a’s
followed by ‘n’ number of b’s
• So, uviw ∉ L. when i = 0.
• This is a contradiction to the assumption that the language is regular.
• So, the language L = {anbn |n≥1) is not regular.
Show that L = {aibj |i>j) is not
regular.
• Step 1:
• Let L is regular and n be the number of states in FA. Consider the
string: x =an+1bn.
• Since Ixl=2n+1≥n, we can split the string x into uvw such that |uv|≤n
and |v| ≥1 as shown below:
• x= an+1bn = am ak abn
u v w
where |u| = m and lv| = k>1 so that |uv| = |u| + |v| = m+k ≤ n which is
true. According to the pumping lemma, uviw ∈ L for i = 0, 1, 2,...
• Step 3: According to the pumping lemma, uviw ∈ L for i = 0, 1, 2,...
• i.e., am ( ak)i abn ∈ L for i ≥0
• If i is 0, i.e., number of a’s in string u will not be more than the
number of b’s in w.
• So, uviw ∉ L. when i = 0.
• This is a contradiction to the assumption that the language is regular.
• So, the language L = {aibj |i>j) is not regular.