What is the difference between language of empty string and empty set language?

27.7k Views Asked by At

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

3

There are 3 best solutions below

2
On BEST ANSWER

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$).

0
On

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).

0
On

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.