Week5 and 6

Q) Prove that there are as many palindromes of length 2n,

defined over Σ = {a,b,c}, as there are of length 2n-1.
Determine the number of palindromes of length 2n
defined over the same alphabet as well.

2
Q) Prove that there are as many palindromes of length 2n,
defined over Σ = {a,b,c}, as there are of length 2n-1.
Determine the number of palindromes of length 2n defined

3
 Task
 Q)
1) Let S={ab, bb} and T={ab, bb, bbbb} Show
that S* = T* [Hint S*  T* and T*  S*]
2) Let S={ab, bb} and T={ab, bb, bbb} Show that S* ≠ T*
But S*  T*
Solution: Since S  T , so every string belonging to
S* , also belongs to T* but bbb is a string belongs to
T* but does not belong to S*.

4
 3) Let S={a, bb, bab, abaab} be a set of strings. Are
abbabaabab and baabbbabbaabb in S*? Does any word in S*
have odd number of b’s?
Solution: since abbabaabab can be grouped as
(a)(bb)(abaab)ab , which shows that the last member of
the group does not belong to S, so abbabaabab is not in S*,
while baabbbabbaabb can not be grouped as members of S,
hence baabbbabbaabb is not in S*. Since each string in S
has even number of b’s so there is no possiblity of any
string with odd number of b’s to be in S*.

5
 Task
Q1)Is there any case when S+ contains Λ? If yes
then justify your answer.
Solution: consider S={Λ,a} then
S+ ={Λ, a, aa, aaa, …}
Here Λ is in S+ as member of S. Thus Λ will
be in S+ , in this case.

6
Q2) Prove that for any set of strings S

i. (S+)*=(S*)*
Solution: In general Λ is not in S+ , while Λ does
belong to S*. Obviously Λ will now be in (S+)*,
while (S*)* and S* generate the same set of
strings. Hence (S+)*=(S*)*.

7
 Q2) continued…
ii) (S+)+=S+
Solution: since S+ generates all possible strings
that can be obtained by concatenating the
strings of S, so (S+)+ generates all possible
strings that can be obtained by concatenating
the strings of S+ , will not generate any new
string.
Hence (S+)+=S+

8
 Q2) continued…
iii) Is (S*)+=(S+)*
Solution: since Λ belongs to S* ,so Λ will
belong to (S*)+ as member of S* .Moreover Λ
may not belong to S+, in general, while Λ will
automatically belong to (S+)*.
Hence (S*)+=(S+)*

9
1
0

Lecture Contents
• Regular Expressions (RE)
• Recursive Definition of RE
• Defining Languages by RE
• Language of Strings
1
1

Regular Expressions

• The language defining symbols

• We are about to create are called Regular
Expressions.
• The languages associated with these regular
expressions are called Regular Languages.
12
13
14
15
16
17
 Regular Expression as * and +
notation
 As discussed earlier that a* generates
Λ, a, aa, aaa, …
and a+ generates a, aa, aaa, aaaa, …, so the
language L1 = {Λ, a, aa, aaa, …} and L2 = {a,
aa, aaa, aaaa, …} can simply be expressed by a*
and a+, respectively.
a* and a+ are called the regular expressions (RE)
for L1 and L2 respectively.
Note: a+, aa* and a*a generate L2.

18
Recursive definition of Regular Expression(RE)
Step 1: Every letter of Σ including Λ is a
regular expression.
Step 2: If r1 and r2 are regular expressions then
1. (r1)

2. r1 r2

3. r1 + r2 and

4. r1*
are also regular expressions.
Step 3: Nothing else is a regular expression.
19
Defining Languages of strings with
Kleene star closure
 Method 3 (Regular Expressions)
 Consider the language L={Λ, x, xx, xxx,…} of
strings, defined over Σ = {x}.
We can write this language as the Kleene star
closure of alphabet Σ or L=Σ*={x}*
this language can also be expressed by the
regular expression x*.
 Similarly the language L={x, xx, xxx,…}, defined
over Σ = {x}, can be expressed by the regular
expression x+.

20
 Now consider another language L, consisting of
all possible strings, defined over Σ = {a,
b}. This language can also be expressed by the
regular expression
(a + b)*.
 Now consider another language L, of strings
having exactly double a, defined over Σ=
{a, b}, then it’s regular expression may be
b*aab*

21
 Now consider another language L, of even
length, defined over Σ = {a, b}, then it’s regular
expression may be
((a+b)(a+b))*
 Now consider another language L, of odd
length, defined over Σ = {a, b}, then it’s regular
expression may be
(a+b)((a+b)(a+b))* or
((a+b)(a+b))*(a+b)

22
 Remark
 It may be noted that a language may be expressed by
more than one regular expressions, while given a
regular expression there exist a unique language
generated by that regular expression.

23
 Example:
 Consider the language, defined over
Σ={a , b} of words having at least one a, may
be expressed by a regular expression
(a+b)*a(a+b)*.
 Consider the language, defined over
Σ = {a, b} of words having at least one a and
one b, may be expressed by a regular
expression
(a+b)*a(a+b)*b(a+b)*+ (a+b)*b(a+b)*a(a+b)*.
24
 Consider the language, defined over
Σ={a, b}, of words starting with double a and
ending in double b then its regular
expression may be aa(a+b)*bb
 Consider the language, defined over
Σ={a, b} of words starting with a and ending
in b OR starting with b and ending in a,
then its regular expression may be
a(a+b)*b+b(a+b)*a

25
Task
 Determine the RE of the language, defined over Σ={a,
b} of words beginning with a.
Solution:
The required RE may be a(a+b)*
 Determine the RE of the language, defined over Σ={a, b}
of words beginning with and ending in same letter.
Solution:
The required RE may be (a+b)+a(a+b)*a+b(a+b)*b

26
2
7

Various Ways representing

Regular Languages

• Tabular
• Descriptive
• Regular Expressions
 Example 10: Ways to represent languages
Consider language T defined over alphabet
Σ = {a,b,c}, & we have to write RE
T = {a, c ,ab, cb, abb, cbb, abbb, cbbb, abbbb, . . . . . .}
Can be expressed in words as,
“All the words in T begin with an a or c and then are
followed by some number of b’s”.

RE = ((a+c)b*) = language(either a or c then some b’s)

28
An important example
The Language EVEN-EVEN :
Language of strings, defined over Σ={a, b} having
even number of a’s and even number of b’s. i.e.
EVEN-EVEN = {Λ, aa, bb, aaaa,aabb,abab, abba, baab,
baba, bbaa, bbbb,…} ,
its regular expression can be written as
(aa+bb+(ab+ba)(aa+bb)*(ab+ba))*

29
 Example 11

Another important language i.e. EVEN-EVEN

“All possible words having even number of a’s
and b’s”

E = [aa+bb+(ab+ba)(aa+bb)*(ab+ba)]*

30
Note
 It is important to be clear about the difference
of the following regular expressions
r1=a*+b*
r2=(a+b)*
Here r1 does not generate any string of
concatenation of a and b, while r2 generates
such strings.

31
 Example 12: Finite Languages

Now consider a finite language L over Σ = {a,

b},
“all the strings of a’s and b’s of length exactly
three.”
L = {aaa aab aba abb baa bab bba bbb}
So what would be the Regular expression ?

R.E = (a+b) (a+b) (a+b) or (a+b)3

32
 Example 13 & 14
Consider another language L over Σ = {a, b},
Example 13: L = {abba, baaa, bbbb}
We can represent L by symbolic expression
L= language (abba+baaa+bbbb)
Example 14: If L is a finite language that includes
that null word Λ , then how can we represent L
through symbolic expression ?
L = {Λ, a aa, bbb}
We can represent L by symbolic expression
L = language (Λ+a+aa+bbb)
33
 Note

It may be noted that if a language contains

even thousand words, its RE may be
expressed, placing ‘+’ between all the
words.

• Here the special structure of RE is not

important.

34
Equivalent Regular Expressions
 Definition:
Two regular expressions are said to be equivalent
if they generate the same language.
Example:
Consider the following regular expressions
r1= (a + b)* (aa + bb)
r2= (a + b)*aa + ( a + b)*bb then
both regular expressions define the language of strings
ending in aa or bb.

35
Note
 If r1 =(aa + bb) and r2=( a + b) then
1. r1+r2 =(aa + bb) + (a + b)
2. r1r2 =(aa + bb) (a + b)
=(aaa + aab + bba + bbb)
3. (r1)* =(aa + bb)*

36
 Operators on Regular Expressions

If r1 = (aa + bb) and r2 = ( a + b) then

Union
r1+r2 = (aa + bb) + (a + b)

Concatenation
r1r2 = (aa + bb) (a + b) = (aaa + aab + bba + bbb)

Closure
(r1)* = (aa + bb)*
37
 Guess Equivalences ?

aa*=a+
a* = (a*)*
(a+b)* = a*b*
(a+b)* = (a+b)* + (a+b)*
(a+b)* = (a+b)* (a+b)*
(a+b)* = a (a+b)*+b (a+b)* + Λ
Note:
All r.e are equivalance……………
38
 Regular Languages
• Languages generated by Regular Expressions are
called Regular Languages.
• It is to be noted that if r1, r2 are regular expressions,
corresponding to the languages L1 and L2 then the
languages generated by
r1+ r2,
r1r2( or r2r1) and
r1*( or r2*)
are also regular languages.

39
Union, Concatenation and Closure of Languages
It is to be noted that if L1 and L2 are expressed
by r1and r2, respectively then the language
expressed by
• r1+ r2, is the language L1 + L2 or L1 L2
• r1r2, is the language L1L2, of strings
obtained by prefixing every string of L1
with every string of L2
• r1*, is the language L1*, of strings obtained
by concatenating the strings of L, including
the null string.
40
 Examples
Example
1. If r1 = (aa+bb) and r2 = (a+b) then the language
of strings generated by r1+r2, is also a regular
language, expressed by (aa+bb) + (a+b)
2. If r1 = (aa+bb) and r2 = (a+b) then the language
of strings generated by r1r2, is also a regular
language, expressed by (aa+bb)(a+b)
3. If r = (aa+bb) then the language of strings
generated by r*, is also a regular language,
expressed by (aa+bb)*
41
Thanks…

42