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).
Kleen PLUS Operation ( + )
Kleen 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
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.
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).
Kleen PLUS Operation ( + )
Kleen 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
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.
Comments
Post a Comment