Prove that the complements of pumping-style languages are context-free

Define $L = L(u,v,x,y,z) = \{uv^ixy^iz : i \geq 0\}$, with $u,v,x,y,z \in \Sigma^*$. Prove that $\overline{L}$ is a CFL for all $u, v, x, y, z$

Clearly, $L$ is a CFL, as it is generated by the grammar:

$S \longrightarrow uAz$

$A \longrightarrow vAy$

$A \longrightarrow x$

I am struggling with this problem, because I don't see how I'd go about constructing a PDA or CFG for $\overline{L}$. The fact that L "looks like" the main condition of the pumping lemma for CFLs must somehow relate, but I am not seeing the connection. Maybe I could do something with morphisms?

The first thing to ask is, why is the claim even true? CFLs, in general, are not closed under compliment, but this language certainly does (yet, it is not regular, so cosure for $\Sigma^*\setminus L$ cannot be used here). So why is the complement a CFL?

The reason is that the language $L$ is actually deterministic context-free, and this class have different closure properties, specifically, it is closed under complementation.

To prove $L$ is a DCFL, we need to build a deterministic PDA for it. There are some technicalities for the case when $v=x$ or $x=y$ or $v=x=y$, but just to give the idea of the construction, let's assume they are all different, $u\ne v\ne x\ne y\ne z$. Since $x,y,u,v,z$ are fixed, it is easy to construct a Deterministic PDA for $L$: it tries to match the input to $u$ (and rejects if it can't), if it finds $u$ it continues to match the input to $v$ at least once (and count the number of times it succeeds, using the stack), the first time it fails, it assumes the input has gotten into the $x$ part, and from there checking the $xy^iz$ part is obvious.

If you reverse the accept/reject of the DPDA of $L$ you will receive a DPDA for $\overline L$, thus also $\overline L$ is deterministic CFL, and specifically, it is a CFL.

StackExchange Computer Science Q#33142, answer score: 3