7
$\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
    $\begingroup$ $\emptyset$: it's a language containing no string: no element. $\{\epsilon\}$: it's a language containing exactly one string, which has length 0 (the empty string, or "" if you will): one element. $\endgroup$ – Clement C. Jan 20 '15 at 14:49
3
$\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$
  • $\begingroup$ I get it. The empty set doesn't have an element but it differs from set containing empty string in that string operations can be performed on it. $\endgroup$ – SphericalCow Jan 20 '15 at 15:11
  • $\begingroup$ @user3688659 - exactly; the theory of formal languages is not dealing with sets, but with strings; set language is used (in the meta-theory) to describe the "mechanism" of formal languages. This "mechanism" needs the empty string, which is a string with $0$ lenght. $\endgroup$ – Mauro ALLEGRANZA Jan 20 '15 at 15:19
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$
0
$\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

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.