Kleene Star Closure of Regular Expressions

Algorithm

The steps to generate the kleene star closure, are:

1. enclose the regular expressions in brackets;
2. append a ^* to the regular expression.

Examples

Consider the regular expression (a+b). The kleene plus of the regular expression is ((a + b))^*.

Bracketting is also necessary in this case. Consider the following regular expression: a + b. If we do not enclose the expression in brackets, the result would be a + b^*, which is different from (a + b)^*. The first describes a language which contains either an a, or else 0 or more bs. The correct result describes a language which has an a or a b, any number of times.

Exercises

Give a regular expression describing the kleene star closure of the following regular expressions:

1. a^*
2. a+b
3. 1+(11)0
4. a+1+b⁺
5. Give a non-trivial (not 1, 0 or a) example where brackets would not be necessary.