String operations

Strings and languages

A string is a finite sequence of characters. The empty string is denoted by ε . The concatenation of two string s and t is denoted by s ⋅ t , or shorter by s t . Concatenating with the empty string makes no difference: s ⋅ ε = s = ε ⋅ s . Concatenation of strings is associative: s ⋅ ( t ⋅ u ) = ( s ⋅ t ) ⋅ u .

For example, ( ⟨ b ⟩ ⋅ ⟨ l ⟩ ) ⋅ ( ε ⋅ ⟨ a h ⟩ ) = ⟨ b l ⟩ ⋅ ⟨ a h ⟩ = ⟨ b l a h ⟩ .

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 S and T are languages, their concatenation S ⋅ T is defined as the set of concatenations of any string from S and any string from T , formally S ⋅ T = { s ⋅ t ∣ s ∈ S ∧ t ∈ T } . Again, the concatenation dot ⋅ is often omitted for brevity.

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

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

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

Alph ⁡ ( s )

The alphabet of a language S is the set of all characters that occur in any string of S , formally: Alph ⁡ ( S ) = ⋃ s ∈ S Alph ⁡ ( s ) .

For example, the set { ⟨ a ⟩ , ⟨ c ⟩ , ⟨ o ⟩ } is the alphabet of the string ⟨ c a c a o ⟩ , and the above D is the alphabet of the above language D ⋅ D ⋅ 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 letters in Σ to languages (possibly in a different alphabet). Thus, for example, given a letter 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 letter a ∈ Σ. String substitutions may be extended to entire languages as

f ( L ) = ⋃ s ∈ L f ( s )

Regular languages are closed under string substitution. That is, if each letter 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 upper case, 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› }.

Another example is the conversion of an EBCDIC-encoded string to ASCII.

String homomorphism

A string homomorphism (often referred to simply as a homomorphism in formal language theory) is a string substitution such that each letter is replaced by a single string. That is, f(a)=s, where s is a string, for each letter a.

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

f⁻¹(s) = { w | f(w) = s }

while the inverse homomorphic image of a language L is defined as

f⁻¹(L) = { s | f(s) ∈ L }

In general, f(f⁻¹(L)) ≠ L, while one does have

f(f⁻¹(L)) ⊆ L

and

L ⊆ f⁻¹(f(L))

for any language 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 f(a) ≠ ε for all a in the alphabet Σ. 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 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 ε.

String projection

If s is a string, and Σ is an alphabet, the string projection of s is the string that results by removing all letters that are not in Σ . It is written as π Σ ( s ) . It is formally defined by removal of letters from the right hand side:

π Σ ( s ) = { ε if  s = ε  the empty string π Σ ( t ) if  s = t a  and  a ∉ Σ π Σ ( t ) a if  s = t a  and  a ∈ Σ

Here ε 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

π Σ ( L ) = { π Σ ( s )   |   s ∈ L }

Right quotient

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

( s a ) / b = { s if  a = b ε if  a ≠ b

The quotient of the empty string may be taken:

ε / a = ε

Similarly, given a subset S ⊂ M of a monoid M , one may define the quotient subset as

S / a = { s ∈ M   |   s a ∈ S }

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

Syntactic relation

The right quotient of a subset S ⊂ M of a monoid M defines an equivalence relation, called the right syntactic relation of S. It is given by

∼ S = { ( s , t ) ∈ M × 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

{ S / m   |   m ∈ 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 letter a from a string s is the removal of the first occurrence of the letter a in the string s, starting from the right hand side. It is denoted as s ÷ a and is recursively defined as

( s a ) ÷ b = { s if  a = b ( s ÷ b ) a if  a ≠ b

The empty string is always cancellable:

ε ÷ a = ε

Clearly, right cancellation and projection commute:

π Σ ( s ) ÷ a = π Σ ( s ÷ a )

Prefixes

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

Pref L ⁡ ( s ) = { t   |   s = t u  for  t , u ∈ Alph ⁡ ( L ) ∗ }

where s ∈ L .

The prefix closure of a language is

Pref ⁡ ( L ) = ⋃ s ∈ L Pref L ⁡ ( s ) = { t   |   s = t u ; s ∈ L ; t , u ∈ Alph ⁡ ( L ) ∗ }

Example:
L = { a b c }  then  Pref ⁡ ( L ) = { ε , a , a b , a b c }

A language is called prefix closed if Pref ⁡ ( L ) = L .

The prefix closure operator is idempotent:

Pref ⁡ ( Pref ⁡ ( L ) ) = Pref ⁡ ( L )

The prefix relation is a binary relation ⊑ such that s ⊑ t if and only if s ∈ Pref L ⁡ ( t ) . This relation is a particular example of a prefix order.