Formal_language

This article is about the term formal language as it is used in mathematics, logic and computer science. For grammar formalism for natural languages, see grammar framework. For information about a mode of expression that is more disciplined or precise than everyday speech, see Register (linguistics).

A formal language can be entirely defined by the way a set of symbols is organized. This way, it can be defined before it has any meaning- without any reference to any meanings of its expressions and before any interpretations are given to it. Formal languages are tools in the field of mathematical logic and computer science. As such they are designed to express the logic of executable programs.

Like languages in linguistics, formal languages generally have two aspects: syntax and semantics. The syntax of a language is what the language looks like without regard to its meaning. The syntax is defined by the set of rules that govern how the symbols of a formal language can be used to construct valid expressions. The semantics is what those expressions mean. This is formalized in various ways, depending on the type of language in question.

A formal language can be identified by its well formed formulas (wffs). The set of well-formed formula of a particular formal language is determined by a fiat of its creator. Usually, the determination of what is and is not a well-formed formula is laid down by designating a) a set of symbols which are the alphabet of the language and b) a set of formation rules which determine what sequences of symbols from the alphabet are the well-formed formula of the language. Hunter, Geoffrey, Metalogic: An Introduction to the Metatheory of Standard First-Order Logic

The branch of mathematics and computer science which studies exclusively the theory of language syntax is known as formal language theory. In formal language theory, a language is nothing more than its syntax; questions of semantics are not addressed in this specialty.

Elementary example

In mathematics, a formal language consists of two parts, an alphabet and rules of syntax. The alphabet is any set of symbols; the rules of syntax define what strings (concatenations of elements of the alphabet) are considered part of the formal language.

As a simple example, consider the alphabet {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, +, =} together with the following rules of syntax:

• Every nonempty string that does not contain + or = and does not start with 0 is in the language.
• The string "0" is in the language.
• A string containing = is in the language if and only if there is exactly one =, and it separates two strings in the language.
• A string containing + is in the language if and only if every + in the string separates two valid strings in the language.
• No string is in the language other than those implied by the previous rules.

Under these rules, the string "23+4=555" is in the language, the string "=234=+" is not. This formal language expresses whole numbers, well-formed addition statements, and well-formed addition equalities, but it expresses only what they look like (their syntax), not what they mean (semantics). For instance, nowhere in these rules is it defined that 0 means the number zero, or that + means addition.

The rest of this article is devoted to the basic notions of formal language theory.

Advanced examples

As an example of a formal language, an alphabet might be $\backslash left\; \backslash \{\; a\; ,\; b\; \backslash right\; \backslash \}$, and a string over that alphabet might be $ababba\backslash ,$.

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

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

Some more examples:

• the set of all words over $\{a,\; b\}\backslash ,$
• the set $\backslash left\; \backslash \{\; a^\{n\}\backslash right\backslash \}$, where $n\backslash ,$ is a natural number and $a^n\backslash ,$ means $a\backslash ,$ repeated $n\backslash ,$ times
• Finite languages, such as $\backslash \{a,b,ab,cba\backslash \}\backslash ,$ or $\backslash \{ac,\; aca,\; bba\backslash \}\backslash ,$
• the set of syntactically correct programs in a given programming language; or
• the set of inputs upon which a certain Turing machine halts; or,
• the set of the longest strings of alphanumeric ASCII characters on this line, (i.e., the set {the, set, of, longest, strings, alphanumeric, ASCII, characters, on, this, line, i, e})

Language specification formalisms

Formal language theory rarely concerns itself with particular languages (except as examples), but is mainly concerned with the study of various types of formalisms to describe languages. For instance, a language can be given as

• A set of strings that can be generated by some grammar (see Chomsky hierarchy);
• A set of strings described or matched by a particular regular expression;
• A set of strings accepted by some automaton, such as a Turing machine or finite state automaton;
• A set of strings for which some decision procedure (an algorithm that asks a sequence of related YES/NO questions) produces the answer YES.

Typical questions asked about such formalisms include:

• What is their expressive power? (Can formalism X describe every language that formalism Y can describe? Can it describe other languages?)
• What is their recognizability? (How difficult is it to decide whether a given word belongs to a language described by formalism X?)
• What is their comparability? (How difficult is it to decide whether two languages, one described in formalism X and one in formalism Y, or in X again, are actually the same language?).

Surprisingly often, the answer to these decision problems is "it cannot be done at all", or "it is extremely expensive" (with a precise characterization of how expensive exactly). Therefore, formal language theory is a major application area of computability theory and complexity theory.

Operations on languages

Certain operations on languages are common. This includes the standard set operations, such as union, intersection, and complementation. Another class of operation is the elementwise application of string operations.

Examples: suppose $\{L\}\_\{1\}$ and $\{L\}\_\{2\}$ are languages over some common alphabet.

• The concatenation $\{L\}\_\{1\}\{L\}\_\{2\}\backslash ,$ consists of all strings of the form $vw\backslash ,$ where $v\backslash ,$ is a string from $\{L\}\_\{1\}\backslash ,$ and $w\backslash ,$ is a string from $\{L\}\_\{2\}\backslash ,$.
• The intersection $\{L\}\_1\; \backslash cap\; \{L\}\_2$ of $\{L\}\_\{1\}\backslash ,$ and $\{L\}\_\{2\}\backslash ,$ consists of all strings which are contained in both languages
• The complement $\backslash neg\; L$ of a language w.r.t. a given alphabet consists of all strings over the alphabet that are not in the language.

Such operations are used to investigate closure properties of classes of languages. A class of languages is closed under a particular operation when the operation, applied to languages in the class, always produces a language in the same class again. For instance, the context-free languages are known to be closed under union, concatenation, and intersection with regular languages, but not closed under intersection or complementation.

Other operations on languages

Some other operations frequently used in the study of formal languages are the following:

• The Kleene star.
• Reversal:
  • Let $e$ be the empty word, then $e^R=e$, and
  • for each non-empty word $w=x\_1...x\_n$ over some alphabet, let $w^R\; =\; x\_n...x\_1$,
  • then for a formal language $L$, $L^R=\backslash \{w^R|w\; \backslash in\; L\backslash \}$.
• Homomorphism and e-free homomorphism.

References

• A. G. Hamilton, Logic for Mathematicians, Cambridge University Press, 1978, ISBN 0 521 21838 1.
• Seymour Ginsburg, Algebraic and automata theoretic properties of formal languages, North-Holland, 1975, ISBN 0 7204 2506 9.
• Michael A. Harrison: Introduction to Formal Language Theory, Addison-Wesley, 1978.
• Grzegorz Rozenberg, Arto Salomaa, Handbook of Formal Languages: Volume I-III, Springer, 1997, ISBN 3 540 61486 9.
• Patrick Suppes, Introduction to Logic, D. Van Nostrand, 1957, ISBN 0 442 08072 7.

See also

• Formal grammar
• Grammar framework
• Formal method
• Formal science
• Formal system
• Mathematical notation
• Metalogic
• Programming language

External links

• B Method.com : his site is designed to present different work and subjects concerning the B method, a formal method with proof
• Formal Language Definitions website 1/24/04
• James Power, Notes on Formal Language Theory and Parsing, 29 November 2002.

Drafts of some chapters in the "Handbook of Formal Language Theory", Vol. 1-3, G. Rozenberg and A. Salomaa (eds.), Springer Verlag, (1997):t

• Alexandru Mateescu and Arto Salomaa, "Preface" in Vol.1, pp. v-viii, and "Formal Languages: An Introduction and a Synopsis", Chapter 1 in Vol. 1, pp.1-39
• Sheng Yu, "Regular Languages", Chapter 2 in Vol. 1
• Jean-Michel Autebert, Jean Berstel, Luc Boasson, "Context-Free Languages and Push-Down Automata", Chapter 3 in Vol. 1
• Christian Choffrut and Juhani Karhumäki, "Combinatorics of Words", Chapter 6 in Vol. 1
• Tero Harju and Juhani Karhumäki, "Morphisms", Chapter 7 in Vol. 1, pp. 439 - 510
• Jean-Eric Pin, "Syntactic semigroups", Chapter 10 in Vol. 1, pp. 679-746
• M. Crochemore and C. Hancart, "Automata for matching patterns", Chapter 9 in Vol. 2
• Dora Giammarresi, Antonio Restivo, "Two-dimensional Languages", Chapter 4 in Vol. 3, pp. 215 - 267

This article is licensed under the GNU Free Documentation License. It uses material from Wikipedia