Empty string: Difference between revisions

Revision as of 16:17, 8 April 2023

Revision as of 16:17, 8 April 2023

Line 1:

{{hatnote|The term {{green|{{big| "" }}}} redirects here. For the printed character, see [[Quotation mark]].}}

""###>all illegal telephone call recording laws a to z access removed <""

{{Short description|Unique string of length zero}}

{{Refimprove|date=November 2009}}

In [[formal language theory]], the '''empty string''', or '''empty word''', is the unique [[String (computer science)|string]] of length zero.

=={{anchor|nullable symbol}}Formal theory==

""###>all illegal telephone call recording laws a to z access removed <""

Formally, a string is a finite, ordered sequence of [[character (symbol)|characters]] such as letters, digits or spaces. The empty string is the special case where the sequence has length zero, so there are no symbols in the string.

There is only one empty string, because two strings are only different if they have different lengths or a different sequence of symbols.

In formal treatments,<ref>{{cite journal |first1=John |last1=Corcoran |first2=William |last2=Frank |first3=Michael |last3=Maloney |title=String theory |journal=Journal of Symbolic Logic |volume=39 |issue=4 |year=1974 |pages=625–637 |doi=10.2307/2272846 |jstor=2272846|s2cid=2168826 }}</ref> the empty string is denoted with '''[[ε]]''' or sometimes '''[[Λ]]''' or '''[[λ]]'''.

The empty string should not be confused with the empty language [[∅]], which is a [[formal language]] (i.e. a set of strings) that contains no strings, not even the empty string.

The empty string has several properties:

* |ε| = 0. Its [[string (computer science)#Formal theory|string length]] is zero.

* ε ⋅ s = s ⋅ ε = s. The empty string is the [[identity element]] of the [[concatenation]] operation. The set of all strings forms a [[free monoid]] with respect to ⋅ and ε.

* ε^R = ε. Reversal of the empty string produces the empty string.

* The empty string precedes any other string under [[lexicographical order]], because it is the shortest of all strings.<ref>[http://cs.fit.edu/~ryan/cse1002/lectures/lexicographic.pdf CSE1002 Lecture Notes – Lexicographic]</ref>

In [[context-free grammar]]s, a [[production (computer science)|production rule]] that allows a [[symbol (logic)|symbol]] to produce the empty string is known as an ε-production, and the symbol is said to be "nullable".

==Use in programming languages==