String operations

In computer science, in the area of formal language theory, frequent use is made of a variety of string functions; however, the notation used is different from that used for computer programming, and some commonly used functions in the theoretical realm are rarely used when programming. This article defines some of these basic terms.
Strings and languages.
A string is a finite sequence of characters.
The empty string is denoted by formula_1.
The concatenation of two string formula_2 and formula_3 is denoted by formula_4, or shorter by formula_5.
Concatenating with the empty string makes no difference: formula_6.
Concatenation of strings is associative: formula_7.
For example, formula_8.
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 formula_9 and formula_10 are languages, their concatenation formula_11 is defined as the set of concatenations of any string from formula_9 and any string from formula_10, formally formula_14.
Again, the concatenation dot formula_15 is often omitted for brevity.
The language formula_16 consisting of just the empty string is to be distinguished from the empty language formula_17.
Concatenating any language with the former doesn't make any change: formula_18,
while concatenating with the latter always yields the empty language: formula_19.
Concatenation of languages is associative: formula_20.
For example, abbreviating formula_21, the set of all three-digit decimal numbers is obtained as formula_22. 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
The alphabet of a language formula_9 is the set of all characters that occur in any string of formula_9, formally:
formula_26.
For example, the set formula_27 is the alphabet of the string formula_28,
and the above formula_29 is the alphabet of the above language formula_22 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
for the empty string ε, and
for string "s" ∈ "L" and character "a" ∈ Σ. String substitutions may be extended to entire languages as 
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.
For the extension of "f"uc to languages, we have e.g.
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, formula_32, where formula_2 is a string, for each character formula_34.
String homomorphisms are monoid morphisms on the free monoid, preserving the empty string and the binary operation of string concatenation. Given a language formula_35, the set formula_36 is called the homomorphic image of formula_35. The inverse homomorphic image of a string formula_2 is defined as
formula_39
while the inverse homomorphic image of a language formula_35 is defined as
formula_41
In general, formula_42, while one does have
formula_43
and
formula_44
for any language formula_35.
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 formula_46 for all "a" in the alphabet formula_47. 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
For the latter language, "g"uc("g"uc−1({ ‹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 formula_47 is an alphabet, the string projection of "s" is the string that results by removing all characters that are not in formula_47. It is written as formula_50. It is formally defined by removal of characters from the right hand side:
Here formula_1 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
Right 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 formula_54. If the string does not have "a" on the right hand side, the result is the empty string. Thus:
The quotient of the empty string may be taken:
Similarly, given a subset formula_57 of a monoid formula_58, one may define the quotient subset as
Left quotients may be defined similarly, with operations taking place on the left of a string.
Hopcroft and Ullman (1979) define the quotient "L"1/"L"2 of the languages "L"1 and "L"2 over the same alphabet as "L"1/"L"2 = { "s" | ∃"t"∈"L"2. "st"∈"L"1 }.
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 {"sa"} / {"b"} yielding {}, rather than { ε }.
The left quotient (when defined similar to Hopcroft and Ullman 1979) of a singleton language "L"1 and an arbitrary language "L"2 is known as Brzozowski derivative; if "L"2 is represented by a regular expression, so can be the left quotient.
Syntactic relation.
The right quotient of a subset formula_57 of a monoid formula_58 defines an equivalence relation, called the right syntactic relation of "S". It is given by
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
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 formula_64 and is recursively defined as
The empty string is always cancellable:
Clearly, right cancellation and projection commute:
Prefixes.
The prefixes of a string is the set of all prefixes to a string, with respect to a given language:
where formula_69.
The prefix closure of a language is
Example: 
formula_71
A language is called prefix closed if formula_72.
The prefix closure operator is idempotent:
The prefix relation is a binary relation formula_74 such that formula_75 if and only if formula_76. This relation is a particular example of a prefix order.