|
Problemy Peredachi Informatsii, 1979, Volume 15, Issue 1, Pages 99–104
(Mi ppi1480)
|
|
|
|
Theory of Languages
On One Class of Grammars with Broken Context Conditions for Employing Productions
B. E. Kats
Abstract:
It is shown that in the class of languages of type $EL+NL$ introduced by Lomkovskaya, the intersection of an arbitrary finite number of languages of the same type is representable in some sense. This implies that the problems of emptiness and finiteness of a language in the class of grammars of type $EL+NL$ and of nonclosedness of the class of languages of type $EL+NL$ relative to homomorphisms are not solvable.
Received: 31.01.1977
Citation:
B. E. Kats, “On One Class of Grammars with Broken Context Conditions for Employing Productions”, Probl. Peredachi Inf., 15:1 (1979), 99–104; Problems Inform. Transmission, 15:1 (1979), 75–79
Linking options:
https://www.mathnet.ru/eng/ppi1480 https://www.mathnet.ru/eng/ppi/v15/i1/p99
|
|