Ogden’s Lemma, Multiple Context-Free Grammars, and the Control Language Hierarchy

I present a simple example of a multiple context-free language for which a very weak variant of generalized Ogden’s lemma fails. This language is generated by a non-branching (and hence well-nested) 3-MCFG as well as by a (non-well-nested) binary-branching 2-MCFG; it follows that neither the class of well-nested 3-MCFLs nor the class of 2-MCFLs is included in Weir’s control language hierarchy, for which Palis and Shende proved an Ogden-like iteration theorem. I then give a simple sufficient condition for an MCFG to satisfy a natural analogue of Ogden’s lemma, and show that the corresponding class of languages is a substitution-closed full AFL which includes Weir’s control language hierarchy. My variant of generalized Ogden’s lemma is incomparable in strength to Palis and Shende’s variant and is arguably a more natural generalization of Ogden’s original lemma.

1. 1.

   Non-branching MCFGs have been called linear in [1].

2. 2.

   The language L in the proof of Theorem 6 was inspired by Lemma 5.4 of Greibach [5], where a much more complicated language was used to show that the range of a deterministic two-way finite-state transducer need not be strongly iterative. One can see that the language Greibach used is an \(\text {8-MCFL}(1)\). In her proof, Greibach essentially relied on a stronger requirement imposed by her notion of strong iterativity, namely that in the factorization \(z = u_1 v_1 \dots u_k v_k u_{k+1}\), there must be some i such that \(u_i\) and \(u_{i+1}\) contain at least one distinguished position and \(v_i\) contains at least two distinguished positions. Strong iterativity is not implied by the condition in Theorem 5, so Greibach’s lemma fell short of providing an example of a language in \(\bigcup _m m\text {-MCFL}(1)\) that does not belong to Weir’s hierarchy.

Authors and Affiliations

1. National Institute of Informatics and SOKENDAI, 2-1-2 Hitotsubashi, Chiyoda-ku, Tokyo, 101-8430, Japan

   Makoto Kanazawa

Corresponding author

Correspondence to Makoto Kanazawa .

Editors and Affiliations

1. Rovira i Virgili University, Tarragona, Spain

   Adrian-Horia Dediu

2. Czech Technical University, Prague, Czech Republic

   Jan Janoušek

3. Rovira i Virgili University, Tarragona, Spain

   Carlos Martín-Vide

4. Justus Liebig University Giessen, Gießen, Germany

   Bianca Truthe

Reprints and permissions

© 2016 Springer International Publishing Switzerland

Policies and ethics