0
$\begingroup$

I'm confused by the use of the empty string as the author uses it below. This is a excerpt from Introduction to the Theory of Computation by Sipser.


enter image description here

enter image description here


Regarding the emptystring line, is this how we define $A^*$, or is it true by definition of the star operation?

I'm confused because he defines the empty string by:


enter image description here


where, if we take the empty string to play the role zero, we see that the empty string is not in all alphabets, and subsequently it is also not in all languages, since a language is defined—verbatim—as: a set of strings.

It appears, from context that the empty string has certain properties of empty set, namely it is a string of all languages, but that is also has properties of zero, as seen in concatenation. It's like the empty string is an substring of all the strings of any language as long as those languages are nonempty sets.

Later on the author states he is going to show that a regular language $A$ is closed under star, but that can't be so—based on these definitions—unless the empty string is in $A$, so which is it?

He defines $A$ as a regular language if it's recognized by some finite automaton, but we don't need the empty string to form such a language, consider the language of all finite strings that include at least one character $\alpha$ then we construct a machine that's in an accepted state when $\alpha$ is read, and remains there for all other inputs. In other words is if $A$ is a regular language then he empty string doesn't seem to have to be in $A$.

$\endgroup$
2
$\begingroup$

The empty string is a string over any alphabet, since the empty set is a finite set. It is not a member of all regular languages, e.g. there are regular languages that consist only of a single nonempty string.

I hope the author does not say every regular language is closed under $*$, because that's certainly not true. What is true is that the set of regular languages is closed under $*$, i.e. if $A$ is a regular language then so is $A^*$.

$\endgroup$
  • $\begingroup$ Yep, I should have read more carefully. He states: "We show that the collection of regular languages is closed under all three regular operations." $\endgroup$ – Zduff Feb 18 at 13:16

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.