Main Page | See live article | Alphabetical index

Formal language

In mathematics, logic and computer science, a formal language is a set of finite-length words (or "strings") over some finite alphabet. Note that we can talk about formal language in many contexts (scientific, legal and so on), meaning a mode of expression more careful and accurate than everyday speech. Use of a particular formal language in the sense intended here is an 'ultimate' version of that usage: formal enough to be used in written form for automatic computation, is a possible criterion.

A typical alphabet would be {a, b}, a typical string over that alphabet would be "ababba", and a typical language over that alphabet containing that string would be the set of all strings which contain the same number of a's as b's. The empty word is allowed and is usually denoted by e, ε or λ. 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.

Some examples of formal languages:

A formal language can be specified in a great variety of ways, such as: Several operations can be used to produce new languages from given ones. Suppose L1 and L2 are languages over some common alphabet. A typical question asked about a formal language is how difficult it is to decide whether a given word belongs to the language. This is the domain of computability theory and complexity theory.