Formal language

From Wikipedia, the free encyclopedia

In mathematics, logic, and computer science, a formal language <math>\boldsymbol{L}</math> consists of a set <math> \boldsymbol{F} </math> of finite-length sequences of elements drawn from a specified finite set <math>\boldsymbol{A}</math> of symbols. Mathematically, it is a unordered pair <math>\boldsymbol{L}=\{\boldsymbol{A},\boldsymbol{F}\}. </math> Among the more common options that are found in applications, a formal language may be viewed as being analogous to

a collection of words

a collection of sentences

In the first case, the set <math>\boldsymbol{A}</math> is called the alphabet of <math>\boldsymbol{L}</math>, and the elements of <math>\boldsymbol{F}</math> are called words. In the second 2, the set <math>\boldsymbol{A}</math> is called the lexicon or the vocabulary of <math>\boldsymbol{F}</math>, while the elements of <math>\boldsymbol{F}</math> are then called sentences. 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.

As an example of formal language, an alphabet might be <math>\left \{ a , b \right \}</math>, and a string over that alphabet might be <math>ababba\,</math>.

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

The empty word (that is, length-zero string) is allowed and is often denoted by <math> e\, </math>, <math> \epsilon\, </math> or <math> \Lambda\, </math>. 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.

1 Examples
2 Specification
3 Operations
4 See also
5 Further reading
6 External links

[edit] Examples

Some examples of formal languages:

the set of all words over <math>{a, b}\,</math>
the set <math>\left \{ a^{n}\right\}</math>, where <math>n\,</math> is a natural number and <math>a^n\,</math> means <math>a\,</math> repeated <math>n\,</math> times
Finite languages, such as <math>\{\{a,b\},\{a, aa, bba\}\}\,</math>
the set of syntactically correct programs in a given programming language; or
the set of inputs upon which a certain Turing machine halts.

[edit] 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 produced 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.

[edit] Operations

Several operations can be used to produce new languages from given ones. Suppose <math>\boldsymbol{L}_{1}</math> and <math>\boldsymbol{L}_{2}</math> are languages over some common alphabet.

The concatenation <math>\boldsymbol{L}_{1}\boldsymbol{L}_{2}\,</math> consists of all strings of the form <math>vw\,</math> where <math>v\,</math> is a string from <math>\boldsymbol{L}_{1}\,</math> and <math>w\,</math> is a string from <math>\boldsymbol{L}_{2}\,</math>.
The intersection <math>\boldsymbol{L}_1 \cap \boldsymbol{L}_2</math> of <math>\boldsymbol{L}_{1}\,</math> and <math>\boldsymbol{L}_{2}\,</math> consists of all strings which are contained in <math>\boldsymbol{L}_{1}\,</math> and also in <math>\boldsymbol{L}_{2}\,</math>.
The union <math>\boldsymbol{L}_1 \cup \boldsymbol{L}_2</math> of <math>\boldsymbol{L}_{1}\,</math> and <math>\boldsymbol{L}_{2}\,</math> consists of all strings which are contained in <math>\boldsymbol{L}_{1}\,</math> or in <math>\boldsymbol{L}_{2}\,</math>.
The complement <math>\complement \boldsymbol{L}_{1}\,</math> of the language <math>\boldsymbol{L}_{1}\,</math> consists of all strings over the alphabet which are not contained in <math>\boldsymbol{L}_{1}\,</math>.
The right quotient <math>\boldsymbol{L}_{1}/\boldsymbol{L}_{2}\,</math> of <math>\boldsymbol{L}_{1}\,</math> by <math>\boldsymbol{L}_{2}\,</math> consists of all strings <math>v\,</math> for which there exists a string <math>w\,</math> in <math>\boldsymbol{L}_{2}\,</math> such that <math>vw\,</math> is in <math>\boldsymbol{L}_{1}</math>.
The Kleene star <math>\boldsymbol{L}_{1}^{*}</math> consists of all strings which can be written in the form <math>w_{1}w_{2}...w_{n}\,</math> with strings <math>w_{i}\,</math> in <math>\boldsymbol{L}_{1}\,</math> and <math>n \ge 0</math>. Note that this includes the empty string <math>\epsilon\,</math> because <math>n = 0\,</math> is allowed.
The reverse <math>\boldsymbol{L}_{1}^{R}\,</math> contains the reversed versions of all the strings in <math>\boldsymbol{L}_{1}\,</math>.
The shuffle of <math>\boldsymbol{L}_{1}\,</math> and <math>\boldsymbol{L}_{2}\,</math> consists of all strings which can be written in the form <math>v_{1}w_{1}v_{2}w_{2}\dots v_{n}w_{n}</math> where <math>n \ge 1</math> and <math>v_{1},\dots,v_{n}\,</math> are strings such that the concatenation <math>v_{1}\dots v_{n}</math> is in <math>\boldsymbol{L}_{1}\,</math> and <math>w_{1},\dots,w_{n}</math> are strings such that <math>w_{1}\dots w_{n}</math> is in <math>\boldsymbol{L}_{2}</math>.

[edit] See also

Language for languages in general
Syntax for the form of a language in general
Semantics for the meanings in a language
Natural language for languages that are not formal
Computer language for application of formal languages in computing
Programming language for the application of formal languages to program computers

[edit] Further reading

Hopcroft, J. & Ullman, J. (1979). Introduction to Automata Theory, Languages, and Computation. Addison-Wesley. ISBN 0-201-02988-X.
Helena Rasiowa and Roman Sikorski (1970). The Mathematics of Metamathematics, 3^rd ed., PWN., chapter 6 Algebra of formalized languages.
Rozemberg, G. & Salomaa, A. (eds.) (1979). Introduction to Automata Theory, Languages, and Computation. Addison-Wesley. ISBN 978-3-540-61486-9.

[edit] External links

http://icalp06.dsi.unive.it/ ICALP 2006 33rd International Colloquium on Automata, Languages and Programming.

http://www.cs.auckland.ac.nz/CDMTCS/conferences/dlt/DLTConfSeries.html International Conferences on Developments in Language Theory

Automata theory: formal languages and formal grammars
Chomsky hierarchy	Grammars	Languages	Minimal automaton
Type-0	Unrestricted	Recursively enumerable	Turing machine
n/a	(no common name)	Recursive	Decider
Type-1	Context-sensitive	Context-sensitive	Linear-bounded
Type-2	Context-free	Context-free	Pushdown
Type-3	Regular	Regular	Finite
Each category of languages or grammars is a proper subset of the category directly above it.