Hierarchy of k-context-free languages part 1

Abstract

Languages generated by context-free grammars by rewriting always exactly k nonterminals simultaneouslyk ≥ 1, are called k-context-free languages. We prove a pumping result for k-context-free languages and using it show that the families of k-languages form a strict hierarchy with respect to k.

The paper is divided into two parts. The main results showing the strictness of the hierarchy of k-languages are presented in Part 2. This first part contains definitions and preliminary results on derivation forests and k-schedules.

Keywords:

• Pattern selector grammars
• schedules

C.R. Categories:

• F.4.2
• F.4.3