Kleene Star Closure, Recursive definition of languages

<< What does automata mean, Introduction to languages

Regular Expression, Recursive definition of Regular Expression >>

Theory of Automata

(CS402)

Theory of Automata

Lecture N0. 2

Reading Material

Chapter 3

Introduction to Computer Theory

Summary

Kleene Star Closure, Plus operation, recursive definition of languages, INTEGER, EVEN, factorial,

PALINDROME, {anbn}, languages of strings (i) ending in a, (ii) beginning and ending in same letters, (iii)

containing aa or bb (iv) containing exactly one a

Kleene Star Closure

Given Σ, then the Kleene Star Closure of the alphabet Σ, denoted by Σ*, is the collection of all strings defined

over Σ, including Λ.

It is to be noted that Kleene Star Closure can be defined over any set of strings.

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. (By infinite language, it is

supposed that the language contains infinite many words, each of finite length).

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, ....}

Remark

It is to be noted that Kleene Star can also be operated on any string i.e. a* can be considered to be all possible

strings defined over {a}, which shows that a* generates Λ, a, aa, aaa, ...

It may also be noted that a+ can be considered to be all possible non empty strings defined over {a}, which

shows that a+ generates a, aa, aaa, aaaa, ...

Recursive definition of languages

The following three steps are used in recursive definition

Some basic words are specified in the language.

Rules for constructing more words are defined in the language.

No strings except those constructed in above, are allowed to be in the language.

Example

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.

Example

Theory of Automata

(CS402)

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.

Example

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.

Defining the language PALINDROME, defined over Σ = {a,b}

a and b are in PALINDROME

Step 1:

if x is palindrome, then s(x)Rev(s) and xx will also be palindrome, where s belongs to Σ*

Step 2:

Step 3:

No strings except those constructed in above, are allowed to be in palindrome

Defining the language {anbn }, n=1,2,3,... , of strings defined over Σ={a,b}

ab is in {anbn}

Step 1:

if x is in {anbn}, then axb is in {anbn}

Step 2:

No strings except those constructed in above, are allowed to be in {anbn}

Step 3:

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

Step 1:

a is in L

if x is in L then s(x) is also in L, where s belongs to Σ*

Step 2:

Step 3:

No strings except those constructed in above, are allowed to be in L

Defining the language L, of strings beginning and ending in same letters , defined over Σ={a, b}

Step 1:

a and b are in L

(a)s(a) and (b)s(b) are also in L, where s belongs to Σ*

Step 2:

Step 3:

No strings except those constructed in above, are allowed to be in L

Defining the language L, of strings containing aa or bb , defined over

Σ={a, b}

Step 1:

aa and bb are in L

s(aa)s and s(bb)s are also in L, where s belongs to Σ*

Step 2:

No strings except those constructed in above, are allowed to be in L

Step 3:

Defining the language L, of strings containing exactly one a, defined over

Σ={a, b}

Step 1:

a is in L

s(aa)s is also in L, where s belongs to b*

Step 2:

Step 3:

No strings except those constructed in above, are allowed to be in L

Table of Contents: