Main Index Computer Science Data Structures
  Subject Index
comment on the page

Symbol

A symbol is an abstract entity that is usually not defined and are used as concrete representations of ideas, concepts, or other abstractions. Symbols are used as elements of a code in a formal notational system. Their interpretation is given by referring to something.  The shape of symbols often is not in relation to its meaning and it neither resembles nor is causally connected to its referent. Its meaning is agreed upon and shared by convention. Examples of frequently used symbols are letters or digits.

A string (a sequence or a  word) is a finite sequence of symbols juxtaposed. For example if are symbols then aabccba is a string. The length of a string , denoted by , is the number of symbols composing the string. The empty string, usually denoted by , is the string consisting of no (zero) symbols, i.e. .  

A prefix of a string is the initial portion of the string. It consists of any number of leading symbols of that string. For example, string aabc has prefixes , a, aa, aab, aabc.  Another example in the context of language, is the word prefix itself. It is made up of the base fix (meaning attach in this case), and the prefix pre, meaning before.

A suffix of a string is any number of its trailing symbols.

A prefix or suffix of a string, other than the string itself, is called a proper prefix or proper suffix.

A substring (a subword or a factor) or a subsequence of a string are subsets of the symbols in a string, where the order of the elements is preserved. More precisely, if   is a string of symbols then a string , where and is called a substring.  On the other hand, the string of the form with and is called a subsequence of .

A substring of a string is a prefix of a suffix of the string, and equivalently a suffix of a prefix. Clearly the notion of a subsequence is a generalization of those of a substring, suffix and prefix.

Given a string, the problem of finding a string occurring in a larger string is called the string searching problem  . To find the longest string which is equal to a subsequence of two or more strings is known as the longest common subsequence problem .

The concatenation of two strings is the string formed by writing the first, followed by the second, with no intervening space.  That is, if ab and ba  are strings, then abba is their concatenation. In other words, juxtaposition is used when symbolizing the concatenation operation.  The empty string is the identity for the concatenation operation. That is, for each string .

The word symbol has its origin in Greek word σύμβολον (sýmbolon) which is composition of the root words συν (syn) meaning together and βολή (bolē) a throw, having the approximate meaning of  to throw together.

Cite this web-page as: