We present a new structural lemma for deterministic con- text free languages. From the first sight, it looks like a pumping lemma, because it is also based on iteration properties, but it has significant distinctions that makes it much easier to apply. The structural lemma is a combinatorial analogue of KC-DCF-Lemma (based on Kolmogorov complexity), presented by Li and Vit ́anyi in 1995 and corrected by Glier in 2003. The structural lemma allows not only to prove that a language is not a DCFL, but discloses the structure of DCFLs Myhill-Nerode classes.
We consider regular realizability problems, which consist in verifying whether the intersection of a regular language which is the problem input and a fixed language (filter) which is a parameter of the problem is nonempty. We study the algorithmic complexity of regular realizability problems for context-free filters. This characteristic is consistent with the rational dominance relation of CF languages. However, as we prove, it is more rough. We also give examples of both P-complete and NL-complete regular realizability problems for CF filters. Furthermore, we give an example of a subclass of CF languages for filters of which the regular realizability problems can have an intermediate complexity. These are languages with polynomially bounded rational indices.