String operations

A string is a finite sequence of characters. The empty string is denoted by \varepsilon. The concatenation of two strings s and t is denoted by s \cdot t, or shorter by s t. Concatenating with the empty string makes no difference: s \cdot \varepsilon = s = \varepsilon \cdot s. Concatenation of strings is associative: s \cdot (t \cdot u) = (s \cdot t) \cdot u. For example, (\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 S and T are languages, their concatenation S \cdot T is defined as the set of concatenations of any string from S and any string from T, formally S \cdot T = \{ s \cdot t \mid s \in S \land t \in T \}. Again, the concatenation dot \cdot is often omitted for brevity. The language \{\varepsilon\} 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 \cdot \{\varepsilon\} = S = \{\varepsilon\} \cdot S, while concatenating with the latter always yields the empty language: S \cdot \{\} = \{\} = \{\} \cdot S. Concatenation of languages is associative: S \cdot (T \cdot U) = (S \cdot T) \cdot U. For example, abbreviating 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 D \cdot D \cdot 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 :\operatorname{Alph}(s) The alphabet of a language S is the set of all characters that occur in any string of S, formally: \operatorname{Alph}(S) = \bigcup_{s \in S} \operatorname{Alph}(s). For example, the set \{\langle a \rangle,\langle c \rangle,\langle o \rangle\} is the alphabet of the string \langle cacao \rangle, and the above D is the alphabet of the above language 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)=La where La ⊆ Δ* 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 :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 fuc(.) to uppercase, which may be defined e.g. as follows: For the extension of fuc to strings, we have e.g. • fuc(‹Straße›) = {‹S›} ⋅ {‹T›} ⋅ {‹R›} ⋅ {‹A›} ⋅ {‹SS›} ⋅ {‹E›} = {‹STRASSE›}, • fuc(‹u2›) = {‹U›} ⋅ {ε} = {‹U›}, and • fuc(‹Go!›) = {‹G›} ⋅ {‹O›} ⋅ {} = {}. For the extension of fuc to languages, we have e.g. • fuc({ ‹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, f(a)=s, where s is a string, for each character 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^{-1}(s) = \{ w \mid f(w) = s \} while the inverse homomorphic image of a language L is defined as f^{-1}(L) = \{ s \mid f(s) \in L \} In general, f(f^{-1}(L)) \neq L, while one does have f(f^{-1}(L)) \subseteq L and L \subseteq f^{-1}(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) \neq \varepsilon for all a in the alphabet \Sigma. Simple single-letter substitution ciphers are examples of (ε-free) string homomorphisms. An example string homomorphism guc can also be obtained by defining similar to the above substitution: guc(‹a›) = ‹A›, ..., guc(‹0›) = ε, but letting guc be undefined on punctuation chars. uc differs from fuc by returning strings, while the latter returned singleton sets of strings. ---> Examples for inverse homomorphic images are • guc−1({ ‹SSS› }) = { ‹sss›, ‹sß›, ‹ßs› }, since guc(‹sss›) = guc(‹sß›) = guc(‹ßs›) = ‹SSS›, and • guc−1({ ‹A›, ‹bb› }) = { ‹a› }, since guc(‹a›) = ‹A›, while ‹bb› cannot be reached by guc. For the latter language, guc(guc−1({ ‹A›, ‹bb› })) = guc({ ‹a› }) = { ‹A› } ≠ { ‹A›, ‹bb› }. The homomorphism guc 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 \Sigma is an alphabet, the string projection of s is the string that results by removing all characters that are not in \Sigma. It is written as \pi_\Sigma(s)\,. It is formally defined by removal of characters from the right hand side: :\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 \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 :\pi_\Sigma (L)=\{\pi_\Sigma(s)\ \vert\ 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 s/a. If the string does not have a on the right hand side, the result is the empty string. Thus: : (sa)/ b = \begin{cases} s & \mbox{if } a=b \\ \varepsilon & \mbox{if } a \ne b \end{cases} The quotient of the empty string may be taken: : \varepsilon / a = \varepsilon Similarly, given a subset S\subset M of a monoid M, one may define the quotient subset as : 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 L1/L2 of the languages L1 and L2 over the same alphabet as . 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 L1 and an arbitrary language L2 is known as Brzozowski derivative; if L2 is represented by a regular expression, so can be the left quotient. ==Syntactic relation==

The right quotient of a subset S\subset M of a monoid M defines an equivalence relation, called the right syntactic relation of S. It is given by :\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 of right quotients is finite; that is, if :\{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. ==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 s\div a and is recursively defined as :(sa)\div b = \begin{cases} s & \mbox{if } a=b \\ (s\div b)a & \mbox{if } a \ne b \end{cases} The empty string is always cancellable: :\varepsilon \div a = \varepsilon Clearly, right cancellation and projection commute: :\pi_\Sigma(s)\div a = \pi_\Sigma(s \div a ) ==Prefixes==

The prefixes of a string is the set of all prefixes to a string, with respect to a given language: :\operatorname{Pref}_L(s) = \{t\ \vert\ s=tu \mbox { for } t,u\in \operatorname{Alph}(L)^*\} where s\in L. The prefix closure of a language is :\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: L=\left\{abc\right\}\mbox{ then } \operatorname{Pref}(L)=\left\{\varepsilon, a, ab, abc\right\} A language is called prefix closed if \operatorname{Pref} (L) = L. The prefix closure operator is idempotent: :\operatorname{Pref} (\operatorname{Pref} (L)) =\operatorname{Pref} (L) The prefix relation is a binary relation \sqsubseteq such that s\sqsubseteq t if and only if s \in \operatorname{Pref}_L(t). This relation is a particular example of a prefix order. ==See also ==