Concerning two-adjacent context-free languages (Q1085985): Difference between revisions

The k-adjacent languages appeared first in a paper of \textit{J. Gonczarowski} and \textit{E. Shamir} [J. Comput. Syst. Sci. 30, 249-273 (1985; Zbl 0601.68057)] as a special case of k-languages. Every context- free language is a k-language as well as a k-adjacent language. For each \(k>1\), there are k-languages which are not context-free. By contrast, very little has been known about the adjacent case. This paper contains the following result: There are 2-adjacent languages which are not context-free and not even E0L-languages. A variant of 2- adjacent languages which contains all E0L-languages is also presented.