2
$\begingroup$

I am grading an exercise in Automata and Formal Languages and see many of the students use $\{\varepsilon\}$ as the empty language. At first I thought this was an error, and I have asked the lecturer who confirmed. But I keep seeing this and I'm losing my confidence. Is this kind of thing used by anyone? Meaning, does anyone use $\{\varepsilon\}$ as the empty language (even though it would "override" the obvious meaning of the singleton of $\varepsilon$)?

$\endgroup$
4
  • $\begingroup$ It is hard to say if a notation is not being used by anyone. You are a witness that someone is using it, your students. On the other hand, the notation $\{\epsilon\}$ is used in set theory to denote the set with one element $\epsilon$. $\endgroup$ – plop Mar 26 at 13:34
  • 2
    $\begingroup$ You don't have a problem with notation, but rather a problem with students' undestanding, namely the difference between "empty language $\{\}$" and "the language containing just the empty word $\{\epsilon\}$". $\endgroup$ – Andrej Bauer Mar 26 at 14:01
  • $\begingroup$ It's a common misunderstanding. $\endgroup$ – Yuval Filmus Apr 1 at 8:50
  • $\begingroup$ There’s also a special notation (which I can’t quite remember) for the regular expression that produces the empty language - the regular language eps produces the regular language consisting of just the empty string. $\endgroup$ – gnasher729 Apr 1 at 14:46
9
$\begingroup$

No, that's the language containing one string: the empty string, which is very much distinct from the empty language. The finite state machine on the left accepts language $\{\}$, the finite state machine on the right accepts language $\{\varepsilon\}$. They are not the same.

FSMs

If a lot of students are confused maybe explicitly show the difference in an exercise/during a lecture.


As an example, we could use the language as a password check. Anyone submitting an accepted word would be let through. Then $\{\}$ means "let no one in" and $\{\varepsilon\}$ means "let anyone that submits a blank password in". Those are quite different indeed!

$\endgroup$
1
  • $\begingroup$ Thanks. I am just grading the exercise, I am not the lecturer. Just needed to know that I was not wrong. $\endgroup$ – Yekhezkel Yovel Mar 26 at 18:00

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.