In mathematics, logic, and computer science, a formal language is a language that is defined by precise mathematical or machine processable formulas. A formal language is typically characterized as a set of finite-length sequences of elements drawn from a specified finite set of symbols. Mathematically, it is an unordered pair . Among the more common options that are found in applications, a formal language may be viewed as being analogous to Euclid, Greek mathematician, 3rd century BC, as imagined by by Raphael in this detail from The School of Athens. ... Logic, from Classical Greek λόγος logos (meaning word, account, reason or principle), is the study of the principles and criteria of valid inference and demonstration. ... Computer science, or computing science, is the study of the theoretical foundations of information and computation and their implementation and application in computer systems. ... In mathematics, a set can be thought of as any collection of distinct objects considered as a whole. ... In mathematics, an ordered pair is a collection of two objects such that one can be distinguished as the first element and the other as the second element (the first and second elements are also known as left and right projections). ...

• a collection of words

or

• a collection of sentences

In the first case, the set is called the alphabet of , and the elements of are called words. In the second, the set is called the lexicon or the vocabulary of , while the elements of are then called sentences. The mathematical theory that treats formal languages in general is known as formal language theory. In computer science, an alphabet is a finite set of characters or digits. ...

As an example of formal language, 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 b.

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 belonging to 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. In computer science, computability theory is the branch of the theory of computation that studies which problems are computationally solvable using different models of computation. ... As a branch of the theory of computation in computer science, computational complexity theory describes the scalability of algorithms, and the inherent difficulty in providing scalable algorithms for specific computational problems. ...

Examples

Some examples of formal languages:

• the set of all words over
• the set , where is a natural number and means repeated times
• Finite languages, such as or
• the set of syntactically correct programs in a given programming language; or
• the set of inputs upon which a certain Turing machine halts.

In mathematics, a natural number can mean either an element of the set {1, 2, 3, ...} (i. ... An artistic representation of a Turing Machine . ...

Specification

A formal language can be specified in a great variety of ways, such as:

• Strings produced by some formal grammar (see Chomsky hierarchy);
• Strings described or matched by a regular expression;
• Strings accepted by some automaton, such as a Turing machine or finite state automaton;
• Strings indicated by a decision procedure (a set of related YES/NO questions) where the answer is YES.

In computer science and linguistics, a formal grammar, or sometimes simply grammar, is a precise description of a formal language — that is, of a set of strings. ... The Chomsky hierarchy is a containment hierarchy of classes of formal grammars that generate formal languages. ... In computing, a regular expression is a string that is used to describe or match a set of strings, according to certain syntax rules. ... An automaton (plural: automata) is a self-operating machine. ... An artistic representation of a Turing Machine . ... Fig. ... In computability theory and computational complexity theory, a decision problem is a question in some formal system with a yes-or-no answer. ...

Operations

Several operations can be used to produce new languages from given ones. Suppose and are languages over some common alphabet.

• The concatenation consists of all strings of the form where is a string from and is a string from .
• The intersection of and consists of all strings which are contained in both languages