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?

  • $\begingroup$ After reading the first two answers (thak you, Vladhagen and copper.hat) I have realized my mistake: The star operation on a set is not a concatenation of the set with itself. It is a concatenation of strings within one same set (language) and has nothing to do with the operation "concatenation of sets", as I believed before. $\endgroup$ – user1713188 Dec 5 '13 at 15:34

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.

  • $\begingroup$ The biggest thing is to think of the Kleene star on a set not as a concatenation of the sets, but rather a concatenation of elements of the set. Usually these two concepts are the same, but here they slightly differ. $\endgroup$ – Vladhagen Dec 3 '13 at 5:56

Here is an equivalent definition that makes the empty string explicit: The Kleene closure $L^*$ of a set of strings $L$ is the smallest set containing $\epsilon$ that is closed under concatenation with $L$.

The set can be constructed 'explicitly' by letting $L_0 = \{ \epsilon \}$, $L_{n+1} = \{x y | x \in L, y \in L_n \} $ for $n = 0,1,2,...$. Then $L^* = \cup_{n=0}^\infty L_n$.

See https://math.stackexchange.com/a/472974/27978 for an answer relevant to concatenation.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.