Browse By

Calendar

December 2024
M T W T F S S
 1
2345678
9101112131415
16171819202122
23242526272829
3031  

Introduction of Theory Of Computation Notes

by admin in Uncategorized
Kleene Closure

Kleene Closure

Now, let us see “What are the two variations of power of an alphabet?” The variations of power of an alphabet are shown below: 

Now, let us see “What is Kleene closure (or Kleene star/ star operator)? Give example”.   

Kleene Star Closure

Definition: 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).

Kleene PLUS Operation (+)

Plus Operation is same as Kleene Star Closure except that it does not generate  Λ (null string), automatically. The Kleene plus is denoted by ∑+ is defined as follows: ∑+=∑1 U ∑2 U ∑3U…….        
Which is the set of words of any length expect the null string i.e., ϵ (∑+) is not of part of ∑+ and hence ϵ  ∑+.

Example

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

Note: ∑*=∑++ ϵ. This can be written as ∑+ = ∑+– ϵ

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, …

Theory of Computation Notes

आशा करता हूँ, कि यह आर्टिकल आपको पसंद आया होगा तो सोच क्या रहे हैं अभी इसी वक्त इसे अपने दोस्तों के साथ सोशल मीडिया पर Share करें।

Thanking You………………धन्यवाद………………..शुक्रिया………………..मेहरबानी…………………..

Read More: InfoKhajana.com covered the following topics in these notes.

References –
cs.stanford.edu
Wikipedia