Empty word

In theoretical and practical computer science , the empty word is a word that does not consist of a single character, i.e. has the length 0. It is also called an empty string . In many programming languages, such a string is represented by a literal , in which the two start and end characters that enclose a character string follow one another directly, e.g. B. "" in Perl or Java .

definition

The empty word above the alphabet is a sequence of elements of length 0. ${\displaystyle \Sigma }$ ${\displaystyle \Sigma }$

Notation

The empty word is usually represented with the Greek letter ( Epsilon for English "empty"), but the Greek letter ( lambda , from German "empty") is often used . Other common representations are as a different spelling of the epsilon, (also for "empty") and as a single element of a multiplicative written monoid . ${\displaystyle \varepsilon }$ ${\displaystyle \lambda }$ ${\displaystyle \epsilon }$ ${\displaystyle e}$ ${\displaystyle 1}$

features

• ${\displaystyle |\varepsilon |=0}$

The length of the empty word is always 0. This property follows directly from the definition.

• ${\displaystyle \forall w\in \Sigma ^{*}:\varepsilon w=w\varepsilon =w}$

The empty word forms the neutral element in the concatenation of words , that is, the concatenation of any word over any alphabet with always results . The set of words that can be formed over the alphabet is the clover ash shell . ${\displaystyle w}$ ${\displaystyle \Sigma }$ ${\displaystyle \varepsilon }$ ${\displaystyle w}$ ${\displaystyle \Sigma ^{*}}$

• ${\displaystyle \varepsilon \in \Sigma ^{*}}$

The empty word is an element of the Kleene shell over any alphabet . In other words, the empty word is over in the set of all words . ${\displaystyle \varepsilon }$ ${\displaystyle \Sigma ^{*}}$ ${\displaystyle \Sigma }$ ${\displaystyle \Sigma }$

• ${\displaystyle \varepsilon ^{R}=\varepsilon }$

The empty word is identical to its reflection and thus a palindrome .

Further features for special applications

An automaton that accepts the empty word using a transition ${\displaystyle \varepsilon }$

The transitions in nondeterministic finite automata are tuples from the transition relation with states . Such a transition means that the machine can change its state from to without reading a character. -Transitions are one of the reasons for nondeterminism. They are identified in the graph as edges that are labeled with. ${\displaystyle \varepsilon }$ ${\displaystyle (q_{1},\varepsilon ,q_{2})}$ ${\displaystyle \Delta }$ ${\displaystyle q_{1},q_{2}}$ ${\displaystyle q_{1}}$ ${\displaystyle q_{2}}$ ${\displaystyle \varepsilon }$ ${\displaystyle \varepsilon }$

Transitions are also possible with push- button machines and mean that the input word is not processed due to this change in status. If the top symbol is replaced by the empty word during a transition when reading the basement content, it is removed from the basement. Finally, the empty word symbolizes the empty basement, which is one of two possible acceptance criteria for push-down machines. ${\displaystyle \varepsilon }$

literature

• John E. Hopcroft , Jeffrey D. Ullman : Introduction to Automata Theory, Formal Languages, and Complexity Theory. 2nd Edition. Pearson Studies, Reading 2002, ISBN 3-8273-7020-5

Web links

Wiktionary: empty word  - explanations of meanings, word origins, synonyms, translations