Formal Language

(redirected from Formal language theory)
Also found in: Dictionary.

formal language

[¦fȯr·məl ′laŋ·gwij]
(computer science)
An abstract mathematical object used to model the syntax of a programming or natural language.

Formal Language


(1) In a broad sense, a formal language is a set of in some way specialized linguistic means that is provided with more or less precisely defined rules for forming expressions (the syntax of the formal language) and for assigning meaning to the expressions (the semantics of the language). Generally speaking, this use of the term “formal language” does not assume any special restrictions on the syntactic structure, semantic rules, or purpose of the language. For example, the expressions “H2O,” voda, eau, “water,” Wasser, and vesi can, in principle, be considered in equal measure elements of the formal language of chemistry.

(2) In logic, a formal, or formalized, language is an interpreted calculus, that is, a formal system with an interpretation. The use of formal languages is characteristic of mathematical logic, which is often defined as “the subject of formal logic as studied through the construction of formal languages.” It should, however, be noted that this definition is by no means an inherent attribute of presentations of mathematical logic. The concept of formal language not only does not generally occur in particular logico-mathematical languages but, strictly speaking, is not even an element of any specific metalanguages. It is, rather, a useful working term in preliminary heuristic elucidations of the subject matter of mathematical logic.


Church, A. Vvedenie v matematicheskuiu logiku, vol. 1. Moscow, 1960. Introduction (subsecs. 00–09). Translated from English.
References in periodicals archive ?
The project, taking place at the interface of mathematics and computer science, has the potential to make a significant impact in three different ways: by advancing the research on Stone duality and formal language theory, by facilitating a new collaboration between the European host institute and a world-leading mathematics department in the USA, and by establishing the applicant~s position as a leading young researcher in his field.
Using tools from formal language theory, we will prove later that NP-hardness still holds for digraphs of maximum outdegree at most 2 and of maximum total degree at most 4.
As in formal language theory there is a key difference between deterministic and nondeterministic finite state machines in probabilistic case.
In formal language theory in computer science, "scattered context grammars" are used to mathematically formalize scattered information processing or the processing of broadly scattered pieces of mutually related information throughout various computer systems.

Full browser ?