Regular Languages, Finite Automata

1
Kleene Star Closure

Given Σ, then the Kleene Star Closure of the alphabet Σ,

denoted by Σ*, is the collection of all strings defined over Σ,
including Λ.

Note: Kleene Star Closure can be defined over any set of

strings

2
Examples
 If Σ = {x}, Then Σ* = {Λ, x, xx, xxx, xxxx, ….}
 If Σ = {0,1}, Then Σ* = {Λ, 0, 1, 00, 01, 10, 11, ….}
 If Σ = {aaB, c}, Then Σ* = {Λ, aaB, c, aaBaaB, aaBc,
caaB, cc, ….}

Note : Languages generated by Kleene Star Closure of set of

strings, are infinite languages.

3
PLUS Operation (+)
Plus Operation is same as Kleene Star Closure except that it
does not generate Λ (null string), automatically.

Example
If Σ = {0,1}, Then Σ+ = {0, 1, 00, 01, 10, 11, ….}
If Σ = {aab, c}, Then Σ+ = {aab, c, aabaab, aabc, caab, cc,
….}

4
Recursive definition of languages

The following three steps are used in recursive definition

A. Some basic words are specified in the language.
B. Rules for constructing more words are defined in the
language.
C. No strings except those constructed in above, are
allowed to be in the language

5
Defining language of INTEGER

 Step 1: 1 is in INTEGER.
 Step 2: If x is in INTEGER then x+1 and x-1 are also in
INTEGER.
 Step 3: No strings except those constructed in above, are
allowed to be in INTEGER.

6
Defining language of EVEN

 Step 1: 2 is in EVEN.
 Step 2: If x is in EVEN then x+2 and x-2 are also in EVEN.
 Step 3: No strings except those constructed in above, are
allowed to be in EVEN.

7
Defining the language factorial

 Step 1: As 0!=1, so 1 is in factorial.

 Step 2: n!=n*(n-1)! is in factorial.
 Step 3: No strings except those constructed in above, are
allowed to be in factorial.

8
Defining the language PALINDROME
Σ = {a,b}

 Step 1: a and b are in PALINDROME

 Step 2: if x is palindrome, then s(x)Rev(s) and xx will also
be palindrome, where s belongs to Σ*
 Step 3: No strings except those constructed in above, are
allowed to be in palindrome

9
Defining the language {� � � � }
Σ={a,b}, as {� � � � : n=1,2,3,…}

Step 1: ab is in {� � � � }
Step 2: if x is in {� � � � }, then a x b is in {� � � � }
Step 3: No strings except those constructed in above, are
allowed to be in {� � � � }

10
Defining the language L
Σ={a,b}, of strings ending in a

 Step 1: a is in L
 Step 2: if x is in L then s(x) is also in L, where s belongs to
Σ*
 Step 3: No strings except those constructed in above, are
allowed to be in L

11
Defining the language L

Σ={a,b}, strings beginning and ending in same letters

 Step 1: a and b is in L
 Step 2: (a)s(a) and (b)s(b) are also in L, where s belongs to
Σ*
 Step 3: No strings except those constructed in above, are
allowed to be in L

12
Defining the language L
Σ={a,b}, strings containing aa or bb

 Step 1: a and b is in L
 Step 2: s(aa)s and s(bb)s are also in L, where s belongs to
Σ*
 Step 3: No strings except those constructed in above, are
allowed to be in L

13
Defining the language L

Σ={a,b}, strings containing exactly one a

 Step 1: a is in L
 Step 2: s(a)s is also in L, where s belongs to b*
 Step 3: No strings except those constructed in above, are
allowed to be in L

14
15
• Regular Expression is one of the language defining
method
• In this method, language is represented in terms of
strings
• It as an expression of strings and operators.
• Operators:
• *  (kleene closure)  [a*]
• +  (kleene plus)  [a+]
• .  (concatenation)  [ab]
• +  (union)  [a+b]

16
Kleene Closure/ Kleene star/ Kleene
operator:
• It is undetermined power, represent infinite number of terms can be
made including empty string.
• Denoted by * (star or asterisk)
• * means (zero or more)
• Example:
• ∑∗= {a}∗ = {^,a,aa,aaa,aaaa,aaaaa……}
• ∑∗= {a,b}∗ = {^,a,b,aa,ab,ba,bb,aaa,aab,aba,bbb,aabb,abab……}
• (ab*a) = {aa,aba,abba,abbba,abbbba,…….}
• (a*bba*) = {bb, abb, bba, abba, aabb, bbaa, aabba, abbaa, aabbaa,….. }

17
Kleene Plus/ Kleene Positive/ Positive
closure:
• It is also undetermined power, represent infinite number of terms
can be made except empty string.
• Denoted by + (plus/ positive)
• + means (one or more)
• Examples:
• ∑+= {a}+ = {a,aa,aaa,aaaa,aaaaa……}
• ∑+= {a,b}+ = {a,b,aa,ab,ba,bb,aaa,aab,aba,bbb,aabb,abab……}
• (ab+a) = {aba,abba,abbba,abbbba,…….}
• (a+bba+= {abba, abbaa, aabba, aabbaa, aaabbaa….. }

18
Extended Regular Exp Notations

• a?  (zero or one a’s)

• [A-Z]  (Range from A to Z)
• [x/y/z]  (either x or y or z)
• xy  (concatenation)
• R*  (zero or more)
• R+  (one or more)

19
Example
• String contains any number of ‘a’ letters
• L = { ^, a, aa, aaa, aaaa, …..}
R.E = ( a*)

• String contains only ‘a’ letters

• L = { a, aa, aaa, aaaa, …..}
R.E = (�+)

20
Example
• Every String starts with ‘a’ and contains any no of b’s. if ∑ = {a,b}

• L = { a, ab, abb, abbb, abbbb, …..}

R.E = ( a . b*)  R.E = (ab*)

21
Example
• Every String contains ‘a’ or ‘b’, if ∑ = {a,b}
• L = { a, b}
• R.E = ( a + b)

• Every String contains any no of ‘a’ or any no of ‘b’, if ∑

= {a,b}
• L = {^, a, b, aa, ab,ba, bb, aaa, aab, aba, baa,
bbb,…..}

• R.E = ( a + b)*
22
Example
• Every string contains any number of “a’s” followed by bb, if ∑ = {a,b}

• L = { bb, abb, aabb, aaabb, aaaabb, ….}

R.E = (a*bb)

23
Example
• Every string contains any number of “ab”, if ∑ = {a,b}

• L = { ^, ab, abab, ababab, abababab, ….}

R.E = (ab)*

24
Example
• Every string contains any number of “a’s” followed by any no of “b’s”,
if ∑ = {a,b}

• L = { ^, a, b, ab, aab, abb, aaa, bbb, aaab, aabb, abbb, bbbb….}

R.E = (a* b*)

25
Example
• Every string contains even number of a’s , if ∑ = {a}

• L = { ^, aa, aaaa, aaaaaa, aaaaaaaa, ….}

R.E = (aa)*

26
Regular Expressions

Regular expressions describe regular languages

Example:
(� + �. �)∗
describes the language
{�, ��}∗= {�, �, ��, ��, ���, ���, . . }

27
Examples

 A regular expression: � + �. � ∗ . (� + �)
 Not a regular expression: � + � +

28
Languages of Regular Expressions

 L(r) : language of regular expression r

 Example
 �((� + �. �)∗ ) = {�, �, ��, ��, ���, ���, … }

29
Definition

 For primitive regular expressions:

 �(�) = �
 �(�) = �
 �(�) = {�}

30
Definition (continued)

 For regular expressions �1 and �2

�(�1 + �2) = �(�1) � �(�2)
�(�1 . �2 ) = �(�1 )�(�2 )
�(�1∗) = (�(�1))∗
� �1 = �( �1 )

31
Example
Regular expression: (� + �). �∗
� � + � . �∗
= � � + � � �∗
= � � + � � �∗
= (�(�) � �(�))(� � )∗
= � � � � ∗
= �, � �, �, ��, ���, . .
= �, ��, ���, . . , �, ��, ��� …

32
Example

 Regular expression � = � + � ∗
� + ��

� � = {�, ��, ��, ���, ��, ���, … }

33
Example

 Regular expression � = �� ∗
�� ∗�

� � = {� 2� � 2� �: �, � ≥ 0}

34
Example

 Regular expression � = 0 + 1 ∗00 0 + 1 ∗

� � = {��� ������� ���������� ��������� 00}

35
Example

 Regular expression � = 1 + 01 ∗(0 + �)

� � = {��� ������� ���ℎ��� ��������� 00}

36
Equivalent Regular Expressions

 Definition: Regular expressions �1 and �2 are equivalent if

�(�1) = �(�2)

37
Example

� � = {��� ������� ���ℎ��� ��������� 00}

�1 = 1 + 01 ∗(0 + �)
�2 = 1∗011∗ ∗ 0 + � + 1∗ 0 + �
�(�1) = � �2 = �
� → �1 and �2 are equivalent regular expression

38
39
 ��������� �������
��������� �� = ��������
������� ����������

40
By definition of regular expressions:
For regular expressions �1and �2

�(�1 + �2) = �(�1) � �(�2)

�(�1 . �2 ) = �(�1 )�(�2 )

�(�1∗) = (�(�1))∗

� �1 = �( �1 )

41
42
 Definition
 A Finite automaton (FA), is a collection of the followings
 Finite number of states, having one initial and some (maybe
none) final states.
 Finite set of input letters (Σ) from which input strings are
formed.
 Finite set of transitions i.e. for each state and for each input
letter there is a transition showing how to move from one state to
another.

43
Example
 Σ = {a,b}
 States: x, y, z where x is an initial state and z is final state.
 Transitions:
 At state x reading a go to state z,
 At state x reading b go to state y,
 At state y reading a, b go to state y
 At state z reading a, b go to state z

44
Example Continued …
 These transitions can be expressed by the following table
called transition table
Old States New States
Reading a Reading b
x- z y
y y y
z+ z z

45
Example Continued …
 It may be noted that the information of an FA, given in the
previous table, can also be depicted by the following
diagram, called the transition diagram, of the given FA
a, b

y
b

x– a, b
a

Z+

46
Example Continued …

 The previous transition diagram is an FA accepting the

language of strings, defined over Σ={a, b}, starting with a.
It may be noted that this language may be expressed by
the regular expression
a (a + b)*

47
Example

 Σ = {a,b}
 States: x, y, where x is both initial and final state.
 Transitions:
 At state x reading a or b go to state y.
 At state y reading a or b go to state x.

48
Example Continued …
 These transitions can be expressed by the following
transition table
Old States New States
Reading Reading
a b
x y y
y x x

49
Example Continued …
 It may be noted that the previous transition table may be
depicted by the following transition diagram.

a, b

x y

a, b

50
Example Continued …
 The previous transition diagram is an FA accepting the
language of strings, defined over Σ={a, b} of even length.
It may be noted that this language may be expressed by
the regular expression

((a+ b) (a + b))*

51
TASK

 Build an FA for the language L of strings, defined over

Σ={a, b}, of odd length.

52
Solution of Task

a,b

– +

a,b

53
Example:
 Consider the language L of strings, defined over Σ={a, b}, starting
with b. The language L may be expressed by RE b(a + b)* , may be
accepted by the following FA a,b

––
b +

a,b
a
1

54
Example:
 Consider the language L of strings, defined over Σ={a, b},
ending in a. The language L may be expressed by RE
(a+b)*a
 This language may be accepted by the following FA
b a a

– +

55
Example continued …
a
a +
––

a b
b

56
Note

 It may be noted that corresponding to a given language

there may be more than one FA accepting that language,
but for a given FA there is a unique language accepted by
that FA.

57
FA1 Corresponding to L1
a,b

––
a
+

b a,b

The language �1 may be expressed by the regular expression a(a + b)*

58
FA2 Corresponding to L2
a,b

 a +

a,b
b

 The language �2 may be expressed by the regular expression a(a + b)* + Λ

59
Example
 Consider the Language L of Strings of length two or more, defined
over Σ = {a, b}, beginning with and ending in same letters.
 The language L may be expressed by the following regular expression
a (a + b)* a + b (a + b)* b
 It is to be noted that if the condition on the length of string is not
imposed in the above language then the strings a and b will then
belong to the language.
 This language L may be accepted by the following FA

60
Example Continued …

b a a

+
a b
–
a b
b
b
+
a

61
Task

 Build an FA accepting the Language L of Strings, defined

over Σ = {a, b}, beginning with and ending in same letters.

62
Thank you !

63