Formal language

From Simple English Wikipedia, the free encyclopedia

This article's English may not be simple
The English used in this article may not be easy for everybody to understand.

You can help Wikipedia by making this page or section simpler.

In mathematics, logic, and computer science, a formal language is a language that is defined by precise mathematical or machine processable formulas. Such a language, is usually defined as a (finite) set of elements. These elements are usually called words of the language or Strings. These Strings come from another set, which is usually called the alphabet.

Among the more common options that are found in applications, a formal language may be viewed as being analogous to

  • a collection of words

or

  • a collection of sentences

In the first case, the set \boldsymbol{A} is called the alphabet of \boldsymbol{L}, and the elements of \boldsymbol{F} are called words. In the second, the set \boldsymbol{A} is called the lexicon or the vocabulary of \boldsymbol{F}, while the elements of \boldsymbol{F} 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 outside of mathematics, logic and computer science to refer to a mode of expression that is more stilted, disciplined or 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 \left \{ a , b \right \}, and a string over that alphabet might 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\,, \epsilon\, or \Lambda\,. 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.

Contents

[edit] Examples

Some examples of formal languages:

  • the set of all words over {a, b}\,
  • the set \left \{ a^{n}\right\}, where n\, is a natural number and a^n\, means a\, repeated n\, times
  • Finite languages, such as \{\{a,b\},\{a, aa, bba\}\}\,
  • 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 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.

[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, 3rd 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