language
Let be an alphabet. We then define the following using the
powers of an alphabet and infinite👁 Mathworld
👁 Planetmath
union, where .
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👁 Mathworld
👁 Planetmath
). 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 :
-
•
,
-
•
,
-
•
The empty set👁 Mathworld
👁 Planetmath
. In the context of languages, is called the empty language. - •
- •
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👁 Mathworld
👁 Planetmath
, 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👁 Mathworld
👁 Planetmath
, 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👁 Mathworld
👁 Planetmath
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.
| Title | language |
| Canonical name | Language |
| Date of creation | 2013-03-22 12:17:10 |
| Last modified on | 2013-03-22 12:17:10 |
| Owner | mps (409) |
| Last modified by | mps (409) |
| Numerical id | 28 |
| Author | mps (409) |
| Entry type | Definition |
| Classification | msc 03C07 |
| Classification | msc 68Q45 |
| Synonym | -free |
| Related topic | Alphabet |
| Related topic | ContextFreeLanguage |
| Related topic | RegularLanguage |
| Related topic | DeterministicFiniteAutomaton |
| Related topic | NonDeterministicFiniteAutomaton |
| Related topic | KleeneStar |
| Related topic | FormalGrammar |
| Related topic | FirstOrderLanguage |
| Related topic | TermsAndFormulas |
| Related topic | Word |
| Defines | string |
| Defines | empty language |
| Defines | substring |
| Defines | proper language |
| Defines | improper language |
| Defines | alphabet of a language |
| Defines | alphabet of a word |
| Defines | finite language |
| Defines | atomic language |