Formal language, machine-representable

2020 Mathematics Subject Classification: Primary: 68Q [MSN][ZBL]

machine-recognizable formal language

The set of all words (cf. Word) such that when processing them a machine moves into one of its distinguished states. Every recursively-countable set of words is a formal language representable by some Turing machine. Most often one considers machine recognition of recursive formal languages. Thus, regular languages and only these are recognized by finite automata (cf. Automaton, finite); context-free languages and only these are recognized by automata with a magazine memory.

In the case when a formal language consists of infinite words (superwords), it is called a superlanguage. The definition of recognition of a superlanguage on a machine differs from the main definition. For example, a word $x$ belongs to a superlanguage recognizable by a finite automaton $\mathfrak A$ if and only, when processing $x$, $\mathfrak A$ moves infinitely often into the distinguished subset of states.

In studying concrete formal languages not given in machine terms (for example, given by means of formal grammars, cf. Grammar, formal), the need often arises to characterize the complexity of the language in some way. One of the most common paths in this direction is to find a suitable class of machines that recognize the languages in question, and to determine the complexity of the languages via the characteristics of the complexity of the machines. On the other hand, the study of a concrete class of machines includes, as a rule, the description of the formal languages that are representable by the machines in this class. Further investigation of machine-representable formal languages is concerned with questions of their relationship with known classes of languages, closure properties (relative to set-theoretic operations, etc.), and questions of an algorithmic or complexity character.

References

[1]	A. N. Maslov, È.D. Stotskiĭ (edd.), Languages and automata , Moscow (1975) (In Russian) (Collection of translations) Zbl 0301.00006

Comments

See also Formal languages and automata.