$\begingroup$

I am reading Introduction to Automata theory by Ullman. It says the empty set and set containing empty string is different. I am unable to understand the difference between them as the empty string doesn't have any character. Forgive me if this is dumb but I can't seem to understand it

$\endgroup$ 1

3 Answers

$\begingroup$

The situation is the same with the emptyset and the number $0$ (zero).

$0$ is a number and the set $\{ 0 \}$ has one member, while the emptyset has no members at all.

Numbers are used to perform operations like "counting" objects; in order to correctly describe these operations, it is useful to introduce a number ($0$) that counts no objects.

In the same way, in order to describe the operations performed on strings, it is useful to introduce the string ($\epsilon$) with no symbols (that has $lenght=0$).

$\endgroup$ 2 $\begingroup$

Here is a program that accepts the language that contains only the empty string:

 s = get_input(); if (s == "") then ACCEPT; else REJECT;

Here is a program that accepts the empty language:

 s = get_input(); REJECT;

They are not the same program! The first one accepts the empty string; the second does not.

$\endgroup$ $\begingroup$

The set containing one empty string has one element. The empty set has zero elements. The one with one element is "bigger" (its cardinality is larger).

$\endgroup$

Your Answer

Sign up or log in

Sign up using Google Sign up using Facebook Sign up using Email and Password Submit

Post as a guest

Post Your Answer Discard

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