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

Question

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

$\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. — Clement C., Jan 20 '15 at 14:49

Mauro ALLEGRANZA · Accepted Answer · 2015-01-20T15:08:17.697

9

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

edited Jan 20 '15 at 15:08

answered Jan 20 '15 at 14:53

Mauro ALLEGRANZA

94,169

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. – SphericalCow Jan 20 '15 at 15:11
@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. – Mauro ALLEGRANZA Jan 20 '15 at 15:19

score 7 · Answer 2 · answered Jan 20 '15 at 15:00

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.

score 1 · Answer 3 · answered Jan 20 '15 at 14:50

1

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

answered Jan 20 '15 at 14:50

5xum

123,496
6
128
204

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

3 Answers3