The definition of formal languages in the meta language of normal forms of knowledge

A.F. Kurgaev, S.M. Grygoryev


The expressive means of the metalanguage of normal forms of knowledge in relation to different level formal languages are investigated. The formal descriptions of a multitude of linguistic examples are given. The graphic metadescription equivalent to the given text description of the interpreter of the universal Turing machine is developed. The description provided of the universal Turing machine interpreter can be applied to solving the task of modelling the behavior of any T-machine (which performs the task of data conversion on its memory tape). The formal definition of the translator of the determined Turing machine is given. The ability to describe in the metalanguage of normal forms of knowledge the interpreting-translating and the translating-translating processes of formulating and solving of a given task, for which a solution exists is substantiated and defined.

Problems in programming 2017; 4: 037-050


meta-language; regular languages; context-free languages; context languages; 0-languages; Turing machines; formal description of languages


International Standard ISO/IEC 14977 : 1996(E). [Electronic resourse]. - Mode of access:

Kurgaev A., Grygoryev S. Utility model patent UA 92484 U, 2014, Bulletin № 16 (in Ukrainian).

Kurgaev, A. The normal forms of knowledge / A.Kurgaev, S.Grygoryev. - Dopov. NAN Ukraine, 2015, № 11. - Р. 36-43 (in Russian). CrossRef

Kurgaev, A. Metalanguage of Normal Forms of Knowledge / A.Kurgaev, S.Grygoryev. - Cybernetics and Systems Analysis. - November 2016, 52(6). - P. 11-20. (in Russian). CrossRef

Ershov, A.P. Preliminary considerations on the lexicon of programming // Cybernetics and computer technology / Ed. V.A. Melnikov. - 1985. - Vyp. 1. - P. 199-210. (in Russian).

Glushkov, V. Algebra. Languages. Programming / V.Glushkov, G.Zeitlin, E.Yushchenko. - K.: Nauk. Dumka, 1978. - 320 p. (in Russian).

Gross M. Theory of formal grammars / M.Gross, A.Lunten. - M.: Mir, 1971. - 294 p. (in Russian).

Chomsky, N. Formal properties of grammars. / Cybernetic collection. New episode. - Moscow: Mir, 1966. - Vyp. 2. - P. 122-230. (in Russian).

Voishvillo E. Concept as a form of thinking: logical-gnoseological analysis / E. Voishvillo. - Moscow: Izd. MSU, 1989. - 239 p. (in Russian).

Kurgaev, A.F. Problem orientation of the architecture of computer systems / A.F. Kurgayev. - Kiev: Steel, 2008. - 540 p. (in Russian).

Teiz, A. Logical approach to artificial intelligence: from classical logic to logical programming / A. Teiz, P. Gribomon, J. Louis et al. - Transl. With fr .; Ed. G.P. Gavrilov. - Moscow: Mir, 1990. - 432 p. (in Russian).

Chomsky, N. Introduction to the formal analysis of natural languages / N. Chomsky, J. Miller. - Cybernetic collection. New episode. - Moscow: Mir, 1965. - Vyp. 1. - P. 229-290. (in Russian).

Chomsky, N. On some formal properties of grammars / Cybernetic collection. - Moscow: Izd-vo inostr. Lit., 1962. - Vyp. 5. - P. 279-311. (in Russian).

Gilbert, D. Foundations of Mathematics: Theory of Evidence / D.Gilbert, P.Bernays. - M oscow: Nauka, 1982. - 652 p. (in Russian).

Kurgaev A. Logical forms of definition of the concept // Control Systems and Computers. - 1998. - № 2. - P. 3-12. (in Russian).

Chomsky, N. Aspects of the Theory of Syntax, MIT Press, Cambridge, MA, 1965.

Fu, K.S. Syntactic Pattern Recognition and Applications. - New Jersey: Prentice-Hall, Inc., Englewood Cliffs, 1982. - 596 p.

Minsky, M.L. Computation: Finite and Infinite Machines. - NY: Prentice-Hall, Englewood Cliffs, 1967.

Kurgaev, A. The Universal Turing Machine Interpreter / A.Kurgaev, S.Grygoryev. - Dopov. NAN Ukraine, 2016, 10. - P. 28-34. (in Russian). CrossRef

Shannon, C.E. A universal Turing machine with two internal states. - Princeton: Automata Studies, 1956. CrossRef



  • There are currently no refbacks.