formal language theory
formal language theory The study of formal languages in the sense of sets of strings. A major branch of formal language theory concerns finite descriptions of infinite languages. Such a representation takes the form of an abstract device for generating or recognizing any string of the language (see grammar, L-system, automaton). This branch of the subject has applications to the syntax of programming languages (as distinct from their semantics, which require quite different mathematical tools). Thus the set of all legal Pascal programs can be thought of as a formal language over the alphabet of Pascal tokens (see lexical analyzer). Grammars provide the basis for describing syntax, while automata underly the design of parsers for it. On the other hand it was the desire to formalize natural languages that led to the initiation of the subject in 1956 by Noam Chomsky.
Automata also provide an abstract model for computation itself, thus linking formal language theory with the study of computability and complexity. Other issues in formal language theory include decidability of properties of languages, closure properties of language classes, and characterizations of language classes (see Dyck language). An example of a long-standing open question is the decidability of equivalence for deterministic pushdown automata.
The subject has been extended beyond the study of strings to include the study of sets of trees, graphs, and infinite strings, resulting in many more applications.
Automata also provide an abstract model for computation itself, thus linking formal language theory with the study of computability and complexity. Other issues in formal language theory include decidability of properties of languages, closure properties of language classes, and characterizations of language classes (see Dyck language). An example of a long-standing open question is the decidability of equivalence for deterministic pushdown automata.
The subject has been extended beyond the study of strings to include the study of sets of trees, graphs, and infinite strings, resulting in many more applications.
More From encyclopedia.com
Formal Language , formal language
1. A language with explicit and precise rules for its syntax and semantics. Examples include programming languages and also logics su… International Language , international language, sometimes called universal language, a language intended to be used by people of different linguistic backgrounds to facilita… Pashto , Pashto (Pushto) One of the two major languages of Afghanistan, the other being Persian. Pashto is spoken by about 12 million people in e Afghanistan… Algol , Algol
Algol Acronym for algorithmic language. The generic name for a family of high-level languages of great significance in the development of compu… Turkish Language , Türkçe; official language of the Republic of Turkey.
Turkish is one of the Turkic languages of the Altaic language family, one of the world's major l… Hungarian Language , Hungarian •antipodean, Crimean, Judaean, Korean •Albion •Gambian, Zambian •lesbian •Arabian, Bessarabian, Fabian, gabion, Sabian, Swabian •amphibian,…
You Might Also Like
NEARBY TERMS
formal language theory