Notation for the union between the finite input alphabet and the empty string. What is the standard notation?

126 Views Asked by At

In the book “Introduction to the Theory of Computation”, the author writes this.

For any alphabet $\Sigma$ we write $\Sigma_{\varepsilon}$ to be $\Sigma \cup \{\varepsilon\}$.

In my formal lecture notes and online resources, I never came across this form of notation.

Is this form of notation a standard way to notate the union between the input alphabet and empty string or was it created by the author for clarity’s sake?

I prefer knowing the standard way to write out the notation to prevent ambiguity in future exams that I may have.

2

There are 2 best solutions below

0
On BEST ANSWER

I think that the standard is that stated in the Wikipedia article formal language:

A word over an alphabet can be any finite sequence (i.e., string) of letters. The set of all words over an alphabet Σ is usually denoted by Σ* (using the Kleene star). The length of a word is the number of letters it is composed of. For any alphabet, there is only one word of length 0, the empty word, which is often denoted by e, ε, λ or even Λ.

0
On

In a monoid, denoted multiplicatively, the standard notation for the identity is $1$. Thus, from a mathematical point of view, the most natural notation for the empty word, which is the identity of the free monoid $\Sigma^*$, is also $1$. The reason why computer scientists have sometimes use another notation is that, in computer science, one often consider the alphabet $\{0, 1\}$.

Thus my personal advice is to denote the empty word by $\varepsilon$ if $1$ is a letter of the alphabet and by $1$ otherwise.