String operations

A string is a finite sequence of characters. The empty string is denoted by ${\displaystyle \varepsilon }$. The concatenation of two string ${\displaystyle s}$ and ${\displaystyle t}$ is denoted by ${\displaystyle s\cdot t}$, or shorter by ${\displaystyle st}$. Concatenating with the empty string makes no difference: ${\displaystyle s\cdot \varepsilon =s=\varepsilon \cdot s}$. Concatenation of strings is associative: ${\displaystyle s\cdot (t\cdot u)=(s\cdot t)\cdot u}$.

For example, ${\displaystyle (\langle b\rangle \cdot \langle l\rangle )\cdot (\varepsilon \cdot \langle ah\rangle )=\langle bl\rangle \cdot \langle ah\rangle =\langle blah\rangle }$.

A language is a finite or infinite set of strings. Besides the usual set operations like union, intersection etc., concatenation can be applied to languages: if both ${\displaystyle S}$ and ${\displaystyle T}$ are languages, their concatenation ${\displaystyle S\cdot T}$ is defined as the set of concatenations of any string from ${\displaystyle S}$ and any string from ${\displaystyle T}$, formally ${\displaystyle S\cdot T=\{s\cdot t\mid s\in S\land t\in T\}}$. Again, the concatenation dot ${\displaystyle \cdot }$ is often omitted for brevity.

The language ${\displaystyle \{\varepsilon \}}$ consisting of just the empty string is to be distinguished from the empty language ${\displaystyle \{\}}$. Concatenating any language with the former doesn't make any change: ${\displaystyle S\cdot \{\varepsilon \}=S=\{\varepsilon \}\cdot S}$, while concatenating with the latter always yields the empty language: ${\displaystyle S\cdot \{\}=\{\}=\{\}\cdot S}$. Concatenation of languages is associative: ${\displaystyle S\cdot (T\cdot U)=(S\cdot T)\cdot U}$.

For example, abbreviating ${\displaystyle D=\{\langle 0\rangle ,\langle 1\rangle ,\langle 2\rangle ,\langle 3\rangle ,\langle 4\rangle ,\langle 5\rangle ,\langle 6\rangle ,\langle 7\rangle ,\langle 8\rangle ,\langle 9\rangle \}}$, the set of all three-digit decimal numbers is obtained as ${\displaystyle D\cdot D\cdot D}$. The set of all decimal numbers of arbitrary length is an example for an infinite language.

The alphabet of a string is the set of all of the characters that occur in a particular string. If s is a string, its alphabet is denoted by

${\displaystyle \operatorname {Alph} (s)}$

The alphabet of a language ${\displaystyle S}$ is the set of all characters that occur in any string of ${\displaystyle S}$, formally: ${\displaystyle \operatorname {Alph} (S)=\bigcup _{s\in S}\operatorname {Alph} (s)}$.

For example, the set ${\displaystyle \{\langle a\rangle ,\langle c\rangle ,\langle o\rangle \}}$ is the alphabet of the string ${\displaystyle \langle cacao\rangle }$, and the above ${\displaystyle D}$ is the alphabet of the above language ${\displaystyle D\cdot D\cdot D}$ as well as of the language of all decimal numbers.

Let L be a language, and let Σ be its alphabet. A string substitution or simply a substitution is a mapping f that maps characters in Σ to languages (possibly in a different alphabet). Thus, for example, given a character a ∈ Σ, one has f(a)=L_a where L_a ⊆ Δ^* is some language whose alphabet is Δ. This mapping may be extended to strings as

f(ε)=ε

for the empty string ε, and

f(sa)=f(s)f(a)

for string s ∈ L and character a ∈ Σ. String substitutions may be extended to entire languages as [1]

${\displaystyle f(L)=\bigcup _{s\in L}f(s)}$

Regular languages are closed under string substitution. That is, if each character in the alphabet of a regular language is substituted by another regular language, the result is still a regular language.[2] Similarly, context-free languages are closed under string substitution.[3][note 1]

A simple example is the conversion f_uc(.) to uppercase, which may be defined e.g. as follows:

For the extension of f_uc to strings, we have e.g.

• f_uc(‹Straße›) = {‹S›} ⋅ {‹T›} ⋅ {‹R›} ⋅ {‹A›} ⋅ {‹SS›} ⋅ {‹E›} = {‹STRASSE›},
• f_uc(‹u2›) = {‹U›} ⋅ {ε} = {‹U›}, and
• f_uc(‹Go!›) = {‹G›} ⋅ {‹O›} ⋅ {} = {}.

For the extension of f_uc to languages, we have e.g.

• f_uc({ ‹Straße›, ‹u2›, ‹Go!› }) = { ‹STRASSE› } ∪ { ‹U› } ∪ { } = { ‹STRASSE›, ‹U› }.

A string homomorphism (often referred to simply as a homomorphism in formal language theory) is a string substitution such that each character is replaced by a single string. That is, ${\displaystyle f(a)=s}$, where ${\displaystyle s}$ is a string, for each character ${\displaystyle a}$.[note 2][4]

String homomorphisms are monoid morphisms on the free monoid, preserving the empty string and the binary operation of string concatenation. Given a language ${\displaystyle L}$, the set ${\displaystyle f(L)}$ is called the homomorphic image of ${\displaystyle L}$. The inverse homomorphic image of a string ${\displaystyle s}$ is defined as

${\displaystyle f^{-1}(s)=\{w|f(w)=s\}}$

while the inverse homomorphic image of a language ${\displaystyle L}$ is defined as

${\displaystyle f^{-1}(L)=\{s|f(s)\in L\}}$

In general, ${\displaystyle f(f^{-1}(L))\neq L}$, while one does have

${\displaystyle f(f^{-1}(L))\subseteq L}$

and

${\displaystyle L\subseteq f^{-1}(f(L))}$

for any language ${\displaystyle L}$.

The class of regular languages is closed under homomorphisms and inverse homomorphisms.[5] Similarly, the context-free languages are closed under homomorphisms[note 3] and inverse homomorphisms.[6]

A string homomorphism is said to be ε-free (or e-free) if ${\displaystyle f(a)\neq \varepsilon }$ for all a in the alphabet ${\displaystyle \Sigma }$. Simple single-letter substitution ciphers are examples of (ε-free) string homomorphisms.

An example string homomorphism g_uc can also be obtained by defining similar to the above substitution: g_uc(‹a›) = ‹A›, ..., g_uc(‹0›) = ε, but letting g_uc be undefined on punctuation chars. Examples for inverse homomorphic images are

• g_uc⁻¹({ ‹SSS› }) = { ‹sss›, ‹sß›, ‹ßs› }, since g_uc(‹sss›) = g_uc(‹sß›) = g_uc(‹ßs›) = ‹SSS›, and
• g_uc⁻¹({ ‹A›, ‹bb› }) = { ‹a› }, since g_uc(‹a›) = ‹A›, while ‹bb› cannot be reached by g_uc.

For the latter language, g_uc(g_uc⁻¹({ ‹A›, ‹bb› })) = g_uc({ ‹a› }) = { ‹A› } ≠ { ‹A›, ‹bb› }. The homomorphism g_uc is not ε-free, since it maps e.g. ‹0› to ε.

A very simple string homomorphism example that maps each character to just a character is the conversion of an EBCDIC-encoded string to ASCII.

If s is a string, and ${\displaystyle \Sigma }$ is an alphabet, the string projection of s is the string that results by removing all characters that are not in ${\displaystyle \Sigma }$. It is written as ${\displaystyle \pi _{\Sigma }(s)\,}$. It is formally defined by removal of characters from the right hand side:

${\displaystyle \pi _{\Sigma }(s)={\begin{cases}\varepsilon &{\mbox{if }}s=\varepsilon {\mbox{ the empty string}}\\\pi _{\Sigma }(t)&{\mbox{if }}s=ta{\mbox{ and }}a\notin \Sigma \\\pi _{\Sigma }(t)a&{\mbox{if }}s=ta{\mbox{ and }}a\in \Sigma \end{cases}}}$

Here ${\displaystyle \varepsilon }$ denotes the empty string. The projection of a string is essentially the same as a projection in relational algebra.

String projection may be promoted to the projection of a language. Given a formal language L, its projection is given by

${\displaystyle \pi _{\Sigma }(L)=\{\pi _{\Sigma }(s)\ \vert \ s\in L\}}$

The right quotient of a character a from a string s is the truncation of the character a in the string s, from the right hand side. It is denoted as ${\displaystyle s/a}$. If the string does not have a on the right hand side, the result is the empty string. Thus:

${\displaystyle (sa)/b={\begin{cases}s&{\mbox{if }}a=b\\\varepsilon &{\mbox{if }}a\neq b\end{cases}}}$

The quotient of the empty string may be taken:

${\displaystyle \varepsilon /a=\varepsilon }$

Similarly, given a subset ${\displaystyle S\subset M}$ of a monoid ${\displaystyle M}$, one may define the quotient subset as

${\displaystyle S/a=\{s\in M\ \vert \ sa\in S\}}$

Left quotients may be defined similarly, with operations taking place on the left of a string.

Hopcroft and Ullman (1979) define the quotient L₁/L₂ of the languages L₁ and L₂ over the same alphabet as L₁/L₂ = { s | ∃t∈L₂. st∈L₁ }.[7] This is not a generalization of the above definition, since, for a string s and distinct characters a, b, Hopcroft's and Ullman's definition implies yielding {}, rather than { ε }.

The left quotient (when defined similar to Hopcroft and Ullman 1979) of a singleton language L₁ and an arbitrary language L₂ is known as Brzozowski derivative; if L₂ is represented by a regular expression, so can be the left quotient.[8]

The right quotient of a subset ${\displaystyle S\subset M}$ of a monoid ${\displaystyle M}$ defines an equivalence relation, called the right syntactic relation of S. It is given by

${\displaystyle \sim _{S}\;\,=\,\{(s,t)\in M\times M\ \vert \ S/s=S/t\}}$

The relation is clearly of finite index (has a finite number of equivalence classes) if and only if the family right quotients is finite; that is, if

${\displaystyle \{S/m\ \vert \ m\in M\}}$

is finite. In the case that M is the monoid of words over some alphabet, S is then a regular language, that is, a language that can be recognized by a finite state automaton. This is discussed in greater detail in the article on syntactic monoids.

The right cancellation of a character a from a string s is the removal of the first occurrence of the character a in the string s, starting from the right hand side. It is denoted as ${\displaystyle s\div a}$ and is recursively defined as

${\displaystyle (sa)\div b={\begin{cases}s&{\mbox{if }}a=b\\(s\div b)a&{\mbox{if }}a\neq b\end{cases}}}$

The empty string is always cancellable:

${\displaystyle \varepsilon \div a=\varepsilon }$

Clearly, right cancellation and projection commute:

${\displaystyle \pi _{\Sigma }(s)\div a=\pi _{\Sigma }(s\div a)}$

The prefixes of a string is the set of all prefixes to a string, with respect to a given language:

${\displaystyle \operatorname {Pref} _{L}(s)=\{t\ \vert \ s=tu{\mbox{ for }}t,u\in \operatorname {Alph} (L)^{*}\}}$

where ${\displaystyle s\in L}$.

The prefix closure of a language is

${\displaystyle \operatorname {Pref} (L)=\bigcup _{s\in L}\operatorname {Pref} _{L}(s)=\left\{t\ \vert \ s=tu;s\in L;t,u\in \operatorname {Alph} (L)^{*}\right\}}$

Example:
${\displaystyle L=\left\{abc\right\}{\mbox{ then }}\operatorname {Pref} (L)=\left\{\varepsilon ,a,ab,abc\right\}}$

A language is called prefix closed if ${\displaystyle \operatorname {Pref} (L)=L}$.

The prefix closure operator is idempotent:

${\displaystyle \operatorname {Pref} (\operatorname {Pref} (L))=\operatorname {Pref} (L)}$

The prefix relation is a binary relation ${\displaystyle \sqsubseteq }$ such that ${\displaystyle s\sqsubseteq t}$ if and only if ${\displaystyle s\in \operatorname {Pref} _{L}(t)}$. This relation is a particular example of a prefix order.

• Comparison of programming languages (string functions)
• Levi's lemma
• String (computer science) — definition and implementation of more basic operations on strings

• Hopcroft, John E.; Ullman, Jeffrey D. (1979). Introduction to Automata Theory, Languages and Computation. Reading, Massachusetts: Addison-Wesley Publishing. ISBN 978-0-201-02988-8. Zbl 0426.68001. (See chapter 3.)