RUS  ENG
Full version
JOURNALS // Problemy Peredachi Informatsii // Archive

Probl. Peredachi Inf., 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.

UDC: 621.391.194

Received: 31.01.1977


 English version:
Problems of Information Transmission, 1979, 15:1, 75–79

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024