where is the element called empty string. A string is an element of , meaning that it is a grouping of symbols from one after another (via concatenation). For example, is a string, and is a different string. A string is also commonly called a word. , like , contains all finite strings except that does not contain the empty string . Given a string , a string is a substring of if for some strings . For example, , and (the empty string) are all substrings of the string .
Definition. A language over an alphabet is a subset of , meaning that it is a set (http://planetmath.org/Set) of strings made from the symbols in the alphabet .
Take for example an alphabet . The following are all languages over :
A language is said to be proper if the empty string does not belong to it: . A proper language is also said to be -free. Otherwise, it is improper. In the examples above, all but the first and the last examples are -free. is a finite language if is a finite set, and atomic if it is a singleton subset of , such as the fourth example above. A language can be arbitrarily formed, or constructed via some set of rules called a formal grammar.
Given a language over , the alphabet of is defined as the maximal subset of such that every symbol in occurs in some word in . Equivalently, define the alphabet of a word to be the set of all symbols that occur in , then is the union of all , where ranges over .
Remark. A language can also be described in terms of “infinite” alphabets. For example, in model theory, a language is built from a set of symbols, together with a set of variables. These sets are often infinite. Another way of generalizing the notion of a language is to allow the strings to have infinite lengths. The way to do this is to think of a string as a partial function from some set to the alphabet such that . Then the length of a string is just . This specializes to the finite case if we take to be the set of all non-negative integers.
|Date of creation||2013-03-22 12:17:10|
|Last modified on||2013-03-22 12:17:10|
|Last modified by||mps (409)|
|Defines||alphabet of a language|
|Defines||alphabet of a word|