[10] The KC-regularity lemma can be generalized in several ways. Prove the following version. Let L be regular and Lx = {y : xy ∈

L}. Let φ be a partial computable function depending only on L that enumerates strings in Σ∗. For each x, if y is the nth string in the complement of Lx enumerated by φ, then C(y) ≤ C(n)+c, with c a constant depending only on L. Use this generalization to give an alternative proof of Example 6.8.4.

Comments. Source: [M. Li and P. Vit´anyi, SIAM J. Comput., 24:2(1995), 398–410].