When my professor introduced regular expressions, he said that the empty string is the simplest regular expression, where it matches everything. How can this be true? I would think the empty string matches nothing, but perhaps I have an incorrect Computer Science understanding of what "null" or "empty" means.
$\begingroup$
$\endgroup$
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
2
The empty regular expression matches one string: the empty string. That's not everything (most strings aren't the empty string) but it also isn't nothing (the empty string is a string, and the regular expression does match it).
In many programming languages with "regular expression" (regex) support, the default when you match a regex against a string is to consider it a match if any substring matches. Since every string has the empty string as a substring, the empty regular expression will match any string. But that convention isn't standard in computer science.
-
$\begingroup$ How does every string have the empty string as the substring? Is this the same logic that the empty set is defined to be a subset of every set? $\endgroup$ May 26 at 22:50
-
$\begingroup$ yes, such statements are known as vacuously true statements(en.wikipedia.org/wiki/Vacuous_truth) $\endgroup$ May 27 at 10:16
$\begingroup$
$\endgroup$
I wonder if you might be getting confused about the difference between the regular expression that matches only the empty string (often written $\varepsilon$, or sometimes written $\lambda$; it recognizes the language $\{\varepsilon\}$) vs a regular expression that does not match any string (often written $\emptyset$; it recognizes the language $\emptyset$, i.e., the empty set) vs the empty regular expression (which, by convention, matches only the empty string).
See What is the difference between the set containing the empty string and the set containing nothing at all?, What's the difference between phi and lambda in regular expression?, What are Lambda productions.
