String operations

Alphabet of a string

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 \mathrm{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 \mathrm{Alph}(S)=\bigcup _{s\in S}\mathrm{Alph}(s)}$.

For example, the set ${\displaystyle \{⟨a⟩,⟨c⟩,⟨o⟩\}}$ is the alphabet of the string ${\displaystyle ⟨cacao⟩}$, 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.

String substitution

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

${\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. Similarly, context-free languages are closed under string substitution.

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› }.

String homomorphism

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}$.

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\mid f(w)=s\}}$

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

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

In general, ${\displaystyle f(f^{-1}(L))\ne 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. Similarly, the context-free languages are closed under homomorphisms and inverse homomorphisms.

A string homomorphism is said to be ε-free (or e-free) if ${\displaystyle f(a)\ne \epsilon }$ for all a in the alphabet ${\displaystyle \mathrm{\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.

String projection

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

${\displaystyle {\pi }_{\mathrm{\Sigma }}(s)=\{\begin{array}{ll}\epsilon & \text{if }s=\epsilon \text{ the empty string}\\ {\pi }_{\mathrm{\Sigma }}(t)& \text{if }s=ta\text{ and }a\notin \mathrm{\Sigma }\\ {\pi }_{\mathrm{\Sigma }}(t)a& \text{if }s=ta\text{ and }a\in \mathrm{\Sigma }\end{array}}$

Here ${\displaystyle \epsilon }$ 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 }_{\mathrm{\Sigma }}(L)=\{{\pi }_{\mathrm{\Sigma }}(s)|s\in L\}}$

Right and left quotient

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{array}{ll}s& \text{if }a=b\\ \epsilon & \text{if }a\ne b\end{array}}$

The quotient of the empty string may be taken:

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

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|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₁ }. 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.

Syntactic relation

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|S/s=S/t\}}$

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

${\displaystyle \{S/m|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.

Right cancellation

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÷a}$ and is recursively defined as

${\displaystyle (sa)÷b=\{\begin{array}{ll}s& \text{if }a=b\\ (s÷b)a& \text{if }a\ne b\end{array}}$

The empty string is always cancellable:

${\displaystyle \epsilon ÷a=\epsilon }$

Clearly, right cancellation and projection commute:

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

Prefixes

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

${\displaystyle {\mathrm{Pref}}_L(s)=\{t|s=tu\text{ for }t,u\in \mathrm{Alph}(L{)}^{\ast }\}}$

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

The prefix closure of a language is

${\displaystyle \mathrm{Pref}(L)=\bigcup _{s\in L}{\mathrm{Pref}}_L(s)=\left\{t|s=tu;s\in L;t,u\in \mathrm{Alph}(L{)}^{\ast }\right\}}$

Example:
${\displaystyle L=\left\{abc\right\}\text{ then }\mathrm{Pref}(L)=\left\{\epsilon ,a,ab,abc\right\}}$

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

The prefix closure operator is idempotent:

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

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