Encyclopedia  |   World Factbook  |   World Flags  |   Reference Tables  |   List of Lists     
   Academic Disciplines  |   Historical Timeline  |   Themed Timelines  |   Biographies  |   How-Tos     
Sponsor by The Tattoo Collection
Formal language
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 (i.e. character strings) drawn from 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}, and a typical string over that alphabet would be

ababba.

A typical language over that alphabet, containing that string, would be the set of all strings which contain the same number of symbols a and b.

The empty word (that is, length-zero string) is allowed and is often denoted by e, ε 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).

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.