Almost Context-Free Languages

Article type: Research Article

Authors: Chytil, Michal P.^{; *}

Affiliations: Charles University, Malostranské nám. 25, 118 00 Praha 1 – Malá Strana, Czechoslovakia

Note: [*] The main part of this paper was written during the author’s stay at the University of Paderborn in February 1984. The draft version was completed during the author’s stay at the University of Jena in June 1984.

Abstract: We define a superclass of the class of context-free languages, denoted ACFL (almost context-free languages) and construct an infinite sequence of non-context-free languages of decreasing complexity, belonging to ACFL. The languages in ACFL share many important properties of context-free languages. For example, a slight generalization of pumping lemma for context-free languages holds also for languages in ACFL. Similarly, some of the questions decidable for context-free languages are decidable in ACFL and start to be undecidable immediately outside the class. ACFL is a full AFL and contains an infinite strictly decreasing chain of full AFLs.

Keywords: Almost context-free language, context-free language, one-way auxiliary pushdown automaton, pumping lemma, abstract family of languages, complexity of computations

DOI: 10.3233/FI-1986-9303

Journal: Fundamenta Informaticae, vol. 9, no. 3, pp. 283-321, 1986