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 on computer programming, and some commonly used functions in the theoretical realm are rarely used when programming. This article defines some of these basic terms. Computer scaence, or computing science, is the study of the theoretical foundations of information and computation and their implementation and application in computer systems. ... In mathematics, logic and computer science, a formal language is a set of finite-length words (i. ... Computer programming (often shortened to programming or coding) is the process of writing, testing, and maintaining the source code of computer programs. ...

Alphabet of a string

The alphabet of a string is a list of all of the letters that occur in a particular string. If s is a string, its alphabet is denoted by In computer science, an alphabet is a finite set of characters or digits. ...

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 , one has f(a) = L_a where is some language whose alphabet is Δ. This mapping may be extended to strings as

for the empty string , and In various branches of mathematics and computer science, strings are sequences of various simple objects (symbols, tokens, characters, etc. ...

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

for string . String substitution may be extended to the entire language as

An example of string substitution occurs in regular languages, which are closed under string substitution. That is, if the letters of a regular language are substituted by other regular languages, the result is still a regular language. A regular language is a formal language (i. ...

String homomorphism

A string homomorphism 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 homomorphisms, preserving 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 In abstract algebra, a homomorphism is a structure-preserving map between two algebraic structures (such as groups, rings, or vector spaces). ... In mathematics, a binary operation is a calculation involving two input quantities, in other words, an operation whose arity is two. ... In various branches of mathematics and computer science, strings are sequences of various simple objects (symbols, tokens, characters, etc. ...

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

Note that, in general, , while one does have

and

for any language L. Simple single-letter substitution ciphers are examples of string homomorphisms. In cryptography, a substitution cipher is a method of encryption by which units of plaintext are substituted with ciphertext according to a regular system; the units may be single letters (the most common), pairs of letters, triplets of letters, mixtures of the above, and so forth. ...

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 which are not in Σ. It is written as . It is formally defined by removal of letters from the right hand side:

Here denotes the empty string. The projection of a string is essentially the same as a projection in relational algebra. In various branches of mathematics and computer science, strings are sequences of various simple objects (symbols, tokens, characters, etc. ...

String projection may be promoted to the projection of a language. Given a formal language L, its projection is given by In mathematics, logic, and computer science, a formal language is a set of finite-length words (i. ...

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:

The quotient of the empty string may be taken:

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

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

Syntactic relation

The right quotient of a subset of a monoid M defines an equivalence relation, called the right syntactic relation of S. It is given by In mathematics, an equivalence relation, denoted by an infix ~, is a binary relation on a set X that is reflexive, symmetric, and transitive. ...

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 this case, S is a recognizable 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. In the theory of computation, a finite state machine (FSM) or finite state automaton (FSA) is an abstract machine that has only a finite, constant amount of memory. ... In mathematics, the syntactic monoid M(L) of a formal language L over an alphabet A is defined as the quotient M(L) = A* / ~L, where ~L denotes the syntactic congruence of L: It can be shown that the syntactic monoid of L is the smallest monoid that recognizes L...

Right cancellation

The right cancellation of a letter a from a string s is the removal of the first occurance of the letter a in the string s, starting from the right hand side. It is denoted as and is recursively defined as

The empty string is always cancellable:

Clearly, right cancellation and projection commute: In quantum Mechanics, we define: [A,B]=AB-BA If [A,B]=0, then we say A, B is commute. ...

Prefixes

The prefixes of a string is the set of all prefixes to a string, with respect to a given language: A subsequence, substring, prefix or suffix of a string is a new string, containing elements from the original, and in the same order. ...

The prefix closure of a language is

A language is called prefix closed if . Clearly, the prefix closure operator is idempotent: In mathematics, an idempotent element is an element which, intuitively, leaves something unchanged. ...

The prefix relation is a binary relation such that if and only if . In mathematics, a binary relation (or a dyadic relation) is an arbitrary association of elements of one set with elements of another (perhaps the same) set. ...

Prefix grammars generate languages that are prefix-closed (with respect to the grammar!). In computer science, a prefix grammar is a grammar, akin to the formal grammars, where strings are built up from a set of base strings by continually replacing prefixes. ...

See also

• String functions (programming)
• Levi lemma

String functions are used in computer programming languages to manipulate a string or query information about a string (some do both). ...

References

• John E. Hopcroft and Jeffrey D. Ullman, Introduction to Automata Theory, Languages and Computation, Addison-Wesley Publishing, Reading Massachusetts, 1979. ISBN 0-201-029880-X. (See chapter 3.)