String (computer Science) Formal Theory String Datatypes

One starts with a non-empty finite set Σ called an alphabet. Elements of this alphabet are called characters. A string (or word) over Σ is any finite sequence of characters from Σ.

A particularly important string is the sequence of no characters, called the empty string. The empty string is often denoted ε or λ. Note that one does not allow infinite sequences of characters.

The set of all strings over Σ is denoted Σ*. One can define a binary operation on Σ* called string concatenation. If s and t are two strings, their concatenation, denoted st, is defined as the sequence of characters in s followed by the sequence of characters in t.

For example, if s = bear and t = hug then st = bearhug and ts = hugbear.

String concatenation is an associative, but non- commutative operation. The empty string serves as the identity elementIn mathematics, an identity element (or neutral element is a special type of element of a set with respect to a binary operation on that set. It leaves other elements unchanged when combined with them. The term identity element is often shortened to ident. In algebraicAbstract algebra Abstract algebra is the field of mathematics concerned with the study of algebraic structures such as groups, rings and fields. The term "abstract algebra" is used to distinguish the field from " elementary algebra" or "high school algebr terms, the set Σ* forms a monoidIn abstract algebra, a branch of mathematics, a monoid is an algebraic structure with a single, associative binary operation and an identity element. In other words, it is a unital semigroup. Definition A monoid is a magma (M, ), i. a set M with binary op under string concatenation. In fact, Σ* is the free monoid generated by Σ.

The length of a string is the number of characters in the string. The length can be any natural numberNatural number can mean either a positive integer ( 1, 2, 3, 4,. or a non-negative integer ( 0, 1, 2, 3, 4,. Natural numbers have two main purposes: they can be used for counting ("there are 3 apples on the table"), or they can be used for ordering ("this. The length of the empty string is 0. Algebraically speaking, the length function defines a monoid homomorphism from Σ* to N (the natural numbers with addition).

A string s is said to be a substring of t if there exist two strings u and v such that t = usv. One, or both, of u and v can be empty. The relationIn mathematics, the concept of binary relation is exemplified by such ideas as "is greater than" and "is equal to" in arithmetic, or "is congruent to" in geometry, or "is an element of" or "is a subset of" in set theory. Definition Formally, a binary rela "is a substring of" defines a partial order on Σ*, the least element of which is the empty string.

More often, especially in computing applications, one is interested in a different kind of ordering on the set of strings. If the alphabet Σ is well-ordered (cf. alphabetical order) one can define a well-ordering on Σ* called lexicographical order. The empty string is also the least element with respect to this ordering.

A set of strings over Σ (i.e. a subset of Σ*) is called a formal language over Σ. Note that while the alphabet is a finite set and every string has finite length, a language may very well have infinitely many member strings. In fact, Σ* itself is always an infinite language. Important examples of formal languages include regular expressions and formal grammars.

2 String datatypes

A string datatype is a datatype modeled on the idea of a formal string. Strings are such an important and useful datatype that they are implemented in nearly every programming language. In some languages they are available as primitive types and in others as composite types.

Although formal strings can have an arbitrary (but finite) length, strings in real languages have limited length. In general, there are two types of string datatypes: fixed length strings which have a fixed maximum length, and variable length strings whose length is not arbitrarly fixed. Most strings in modern programming languages are variable length strings. Despite the name, even variable length strings are limited in length; although, generally, the limit depends only on the amount of memory available.

String datatypes also differ by the alphabet over which they are defined. Some strings are designed to work over a single fixed alphabet (such as the Latin alphabet or the characters representable by ASCII) and others over an arbitrary alphabet. For example, in the C++ standard library strings are designed as templates definable over any alphabet of characters.

3 Representations

Representations of strings depend heavily on the choice of character set (such as an alphabet) and the method of character encoding. Older string implementations were designed to work with the character set and encoding defined by ASCII, or more recent extensions like the ISO 8859 series. Modern implementations often use the extensive character set defined by Unicode along with a variety of complex enodings such as UTF-8 and UTF-16.

Most string implementations are very similar to variable-length arrays with the entries storing the character codes of corresponding characters. The principal diffence is that, with certain encodings, a single logical character may take up more than one entry in the array. This happens for example with UTF-8, where single characters can take anywhere from one to four bytes. In these cases the logical length of the string differs from the logical length of the array.

The length of a string can be stored implicitly by using a special terminating character; often this is the null character having value zero, a convention used and perpetuated by the popular C programming language. The length of a string can also be stored explicitly, for example by prefixing the string with integer value (convention used in Pascal). Note that with terminated strings the terminating character is not an allowable character in any string.

Here is an example of a null-terminated string stored in a 10 byte buffer, along with its ASCII representation:

F	R	A	N	K	NUL	k	e	f	w
46	52	41	4E	4B	00	6B	65	66	77

The length of a string in the above example 5 characters, but note that it occupies 6 bytes. Characters after the terminator do not form part of the representation; they may be either part of another string or just garbage.

Here is the equivalent Pascal string:

length	F	R	A	N	K	k	f	f	w
05	46	52	41	4E	4B	6B	66	66	77

While these representations are common, others are possible. Using ropes makes certain string operations, such as insertions, deletions, and concatenations more efficient.

4 String algorithms

There are many algorithms for processing strings, each with various tradeoffs. Some categories of algorithms include:

string searching algorithms for finding a given substring or pattern
sorting algorithms
regular expression algorithms
parsing a string

Advanced string algorithms often employ complex mechanisms and data structures, among them suffix trees and finite state machines.

5 String oriented languages and utilities

Strings are such a useful datatype that several languages have been designed in order to make string processing applications easy to write. Examples include:

Many UNIX utilities perform simple string manipulations and can be used to easily program some powerful string processing algorithms. Files and finite streams may be viewed as strings.

Recent scripting languages, including Perl, Python, Ruby, and Tcl employ regular expressions to facilitate text operations.

6 See also

See string for alternate meanings of the word.

Computer terminology Formal languages

<Hide>

Home > String (computer science)

1 Formal theory