Wikipedia / String operations
Wikipedia / 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. Concatenation of strings is associative.
.
A language is often omitted for brevity.
.
. 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.
, and the above is the alphabet of the above 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
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.
String homomorphisms are monoid morphisms on the free monoid, preserving the empty string and the binary operation of string concatenation is called the homomorphic image. The inverse homomorphic image is defined as
is defined as
, while one does have
and
.
The class of regular languages is closed under homomorphisms and inverse homomorphisms. Similarly, the context-free languages are closed under homomorphisms and inverse homomorphisms.
for all a. 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. 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 an alphabet, the string projection of s. It is formally defined by removal of characters from the right hand side:
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 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. 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:
, 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 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
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 of 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 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:
.
The prefix closure of a language is
Example:
A language is called prefix closed.
The prefix closure operator is idempotent:
The prefix relation is a binary relation. This relation is a particular example of a prefix order.
See also
String (computer science) definition and implementation of more basic operations on strings
Notes
References
(See chapter 3.)