Introduction to Kleene Plus and Kleene Closure
In 1951, S Kleene was studying a mathematical model of neurons. They are like Finite State machines in that they do not have scratch memory. He noted patterns in the languages that are recognized by such devices. He realized that in the Theory of computation, languages are not only set having standard set operations such as union, intersection, and complementation which are applied to the languages. Apart from those sets of operations, he proposed two more important operations that were closed under such languages as concatenation and closure. Concatenation is termed as Kleene Plus, denoted by Σ+. And closure which is termed as Kleene star or Kleene closure denoted by Σ∗.
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 the same as Kleene Star Closure except that it does not generate Λ (null string), automatically.
Examples
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, …
