Almost Context-Free Languages

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.