Namespaces
Variants
Actions

Difference between revisions of "Formal language, machine-representable"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
(TeX)
Line 1: Line 1:
 +
{{TEX|done}}
 
''machine-recognizable formal language''
 
''machine-recognizable formal language''
  
 
The set of all words (cf. [[Word|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|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|Automaton, finite]]); context-free languages and only these are recognized by automata with a magazine memory.
 
The set of all words (cf. [[Word|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|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|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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040840/f0408401.png" /> belongs to a superlanguage recognizable by a finite automaton <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040840/f0408402.png" /> if and only, when processing <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040840/f0408403.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040840/f0408404.png" /> moves infinitely often into the distinguished subset of states.
+
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$, $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|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.
 
In studying concrete formal languages not given in machine terms (for example, given by means of formal grammars, cf. [[Grammar, formal|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.

Revision as of 12:53, 9 April 2014

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$, $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] , Languages and automata , Moscow (1975) (In Russian) (Collection of translations)


Comments

See also Formal languages and automata.

How to Cite This Entry:
Formal language, machine-representable. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Formal_language,_machine-representable&oldid=31430
This article was adapted from an original article by S.S. Marchenkov (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article