Incomputer science, in the area offormal language theory, frequent use is made of a variety ofstring functions; however, the notation used is different from that used forcomputer programming, and some commonly used functions in the theoretical realm are rarely used when programming. This article defines some of these basic terms.

A string is a finite sequence of characters.Theempty string is denoted by${\displaystyle \epsilon }$.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 \epsilon =s=\epsilon \cdot s}$.Concatenation of strings isassociative:${\displaystyle s\cdot (t\cdot u)=(s\cdot t)\cdot u}$.

For example,${\displaystyle (⟨b⟩\cdot ⟨l⟩)\cdot (\epsilon \cdot ⟨ah⟩)=⟨bl⟩\cdot ⟨ah⟩=⟨blah⟩}$.

Alanguage 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\wedge t\in T\}}$.Again, the concatenation dot${\displaystyle \cdot }$ is often omitted for brevity.

The language${\displaystyle \{\epsilon \}}$ 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 \{\epsilon \}=S=\{\epsilon \}\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=\{⟨0⟩,⟨1⟩,⟨2⟩,⟨3⟩,⟨4⟩,⟨5⟩,⟨6⟩,⟨7⟩,⟨8⟩,⟨9⟩\}}$, 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.

Thealphabet of a string is the set of all of the characters that occur in a particular string. Ifs is a string, itsalphabet is denoted by

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

Thealphabet 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 theabove${\displaystyle D}$ is the alphabet of theabove language${\displaystyle D\cdot D\cdot D}$ as well as of the language of all decimal numbers.

LetL be alanguage, and let Σ be its alphabet. Astring substitution or simply asubstitution is a mappingf that maps characters in Σ to languages (possibly in a different alphabet). Thus, for example, given a charactera ∈ Σ, one hasf(a)=L_a whereL_a ⊆ Δ^* is some language whose alphabet is Δ. This mapping may be extended to strings as

f(ε)=ε

for theempty string ε, and

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

for strings ∈L and charactera ∈ Σ. 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 conversionf_uc(.) to uppercase, which may be defined e.g. as follows:

For the extension off_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 off_uc to languages, we have e.g.

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

Astring homomorphism (often referred to simply as ahomomorphism informal 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 aremonoid morphisms on thefree monoid, preserving the empty string and thebinary operation ofstring concatenation. Given a language${\displaystyle L}$, the set${\displaystyle f(L)}$ is called thehomomorphic image of${\displaystyle L}$. Theinverse 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.^[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)\ne \epsilon }$ for alla in the alphabet${\displaystyle \mathrm{\Sigma }}$. Simple single-lettersubstitution ciphers are examples of (ε-free) string homomorphisms.

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

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

For the latter language,g_uc(g_uc⁻¹({ ‹A›, ‹bb› })) =g_uc({ ‹a› }) = { ‹A› } ≠ { ‹A›, ‹bb› }.The homomorphismg_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 anEBCDIC-encoded string toASCII.

Ifs is a string, and${\displaystyle \mathrm{\Sigma }}$ is an alphabet, thestring projection ofs 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:

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

String projection may be promoted to theprojection of a language. Given aformal languageL, its projection is given by

${\displaystyle {\pi }_{\mathrm{\Sigma }}(L)=\{{\pi }_{\mathrm{\Sigma }}(s)|s\in L\}}$^{[citation needed]}

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

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.^{[citation needed]}

Hopcroft and Ullman (1979) define the quotientL₁/L₂ of the languagesL₁ andL₂ over the same alphabet asL₁/L₂ = {s | ∃t∈L₂.st∈L₁ }.^[7]This is not a generalization of the above definition, since, for a strings and distinct charactersa,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 languageL₁ and an arbitrary languageL₂ is known asBrzozowski derivative; ifL₂ is represented by aregular expression, so can be the left quotient.^[8]

The right quotient of a subset${\displaystyle S\subset M}$ of a monoid${\displaystyle M}$ defines anequivalence relation, called therightsyntactic relation ofS. 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 right quotients is finite; that is, if

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

is finite. In the case thatM is the monoid of words over some alphabet,S is then aregular language, that is, a language that can be recognized by afinite-state automaton. This is discussed in greater detail in the article onsyntactic monoids.^{[citation needed]}

Theright cancellation of a charactera from a strings is the removal of the first occurrence of the charactera in the strings, starting from the right hand side. It is denoted as${\displaystyle s÷a}$ and is recursively defined as

The empty string is always cancellable:

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

Clearly, right cancellation and projectioncommute:

${\displaystyle {\pi }_{\mathrm{\Sigma }}(s)÷a={\pi }_{\mathrm{\Sigma }}(s÷a)}$^{[citation needed]}

Theprefixes of a string is the set of allprefixes 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}$.

Theprefix 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 calledprefix closed if${\displaystyle \mathrm{Pref}(L)=L}$.

The prefix closure operator isidempotent:

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

Theprefix relation is abinary 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 aprefix order.^{[citation needed]}

• 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.)

• Formal languages
• Relational algebra
• String (computer science)

• All articles with unsourced statements
• Articles with unsourced statements from August 2017