[37] A deterministic CFL (DCFL) language is a language that is accepted by a deterministic pushdown automaton.

(a) Show that {xxR : x ∈ Σ∗} and {xx : x ∈ Σ∗} are not DCFL languages, using an incompressibility argument.

(b) Similar to Lemma 6.8.1, the following is a criterion separating DCFL from CFL. Prove it. Let L ⊆ Σ∗ be a DCFL and c a constant. Let x and y be fixed finite words over Σ and ω a computable sequence over Σ. Let u be a suffix of yy ... yx, v a prefix of ω, and w ∈ Σ∗ such that 1. v can be described in c bits given Lu in lexicographic order;
2. w can be described in c bits given Luv in lexicographic order; and 3. C(v) ≥ 2 log log l(u).
Then there is a constant c depending only on L,

c, x, y, ω such that C(w) ≤ c
.

(c) Use

(b) to prove (a).
Comments. Source: [M. Li and P. Vit´anyi, Ibid.]. In that paper, an incompressibility criterion more general than Item

(b) is given for separating DCFL from CFL. See also [S. Yu, Inform. Process. Lett., 31(1989), 47–51] and [M.A. Harrison, Introduction to Formal Language Theory, Addison-Wesley, 1978] for basics of formal language theory and traditional approaches to this problem such as iteration lemmas.