In the book "Introduction to the Theory of Computation" by Michael Sipser,
in the section 1.3 Regular Expressions:
The symbol ε represents the emty string, which may be a valid element of a language: L = {ε}.
The symbol ∅ represents an empty set; a language that has no strings: ∅ = { }.
On the page 65 of the mentioned book 12 examples of regular expressions are given. The examples 11 and 12 are:
11) 1∗∘∅ = ∅.
Concatenating the empty set to any set yields the empty set.
12) ∅∗ = {ε}.
The star operation puts together any number of strings from the language
to get a string in the result. If the language is empty, the star operation can
put together 0 strings, giving only the empty string.
(In the examples above the ∗ is the Kleen star and in the book is written as exponent. The ∘ is the concatenation operator.)
I believe I understand the rule 11, as explained here: Understanding concatenating the empty set to any set.
My problem is understanding the example 12. It seems to me that the example 12 is contradicting the example 11.
The explanation of the 12th example is based on the fact that the star operation produces a string, and therefore the answer should be some string, and since the concatenated sets are all empty, the resulting string is empty.
But according to me, by the example 11 it follows that ∅∗ = ∅∗∘∅ = ∅ in all cases: 0 empty sets in ∅∗, 1 empty set in ∅∗, 2 empty sets in ∅∗, etc.
Why is the reasoning given in the example 11 not applied in the example 12?
Best Answer
This is one of those odd cases where we need to apply the definition of Kleene star directly. This should be definition 1.23 in your text. (I have the second edition, so the third edition could be different if you have that.) Below this definition there is a paragraph about Kleene Star. Since we can have any number of strings from the set concatenated together, we can have no strings (I.e the empty string). Every set Kleene starred contains the empty string.