|
In mathematics, logic, and computer science, a formal language L is a set of finite-length sequences of elements drawn from a specified finite set A of symbols. Among the more common options that are found in applications, a formal language may be viewed as being analogous to (1) a collection of words or (2) a collection of sentences. In Case 1, the set A is called the alphabet of L, whose elements are called words. In Case 2, the set A is called the lexicon or the vocabulary of L, whose elements are then called sentences. In any case, the mathematical theory that treats formal languages in general is known as formal language theory. Although it is common to hear the term formal language used in other contexts to refer to a mode of expression that is more disciplined or more precise than everyday speech, the sense of formal language discussed in this article is restricted to its meaning in formal language theory. An alphabet might be , and a string over that alphabet might be . A typical language over that alphabet, containing that string, would be the set of all strings which contain the same number of symbols and . The empty word (that is, length-zero string) is allowed and is often denoted by , or . While the alphabet is a finite set and every string has finite length, a language may very well have infinitely many member strings (because the length of words in it may be unbounded). A question often asked about formal languages is "how difficult is it to decide whether a given word belongs to a particular language?" This is the domain of computability theory and complexity theory.
Examples Some examples of formal languages: Specification A formal language can be specified in a great variety of ways, such as: Operations Several operations can be used to produce new languages from given ones. Suppose and are languages over some common alphabet. See also Further reading | ||||||||
|
| |||||||||
 |
|
| |