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.


Both Ran and Yuval indicate that we obtain a CFL, but that we have to take care of technicalities. In particular that we have to check the relation between the different strings $u,v,x,y,z$. After some pondering I think that we can argue without special cases, working with a grammar rather than a PDA.

Let us define "blocks", these are strings of a certain length, without predefined content. Let $U,V,X,Y,Z$ be blocks of length $|u|,|v|,|x|,|y|,|z|$, respectively.

If a string cannot be divided into blocks $UV^iXY^iZ$, i.e., its length is not of the form $|uxz|+i|vy|$, it belongs to the complement. That is a regular language.

All other strings can be derived by your initial grammar, in "block form". $S\to UAZ$, $A\to VAY$, $A\to X$. Now force the grammar to make at least one mistake. By this I mean at one point it generates block $U$ which is not equal to $u$, or block $u$ which is not equal to $v$, etc.


One way to solve this is to consider the language $$ L' = \overline{L} \setminus \overline{uv^*xy^*z}. $$ For "generic" $v,x,y$, it will be the case that $$ L' = \{ uv^ixy^{i+j}z, uv^{i+j}xy^iz : i \geq 0, j \geq 1 \}, $$ and we're done. However, this expression for $L'$ is invalid, for example, when $v=x=y$. Nevertheless, this approach probably works after you handle the "atypical" cases. (Since this expression is valid when $=$ is replaced by $\subseteq$, it is enough to determine for which $i,j$ the words $uv^ixy^{i+j}z,uv^{i+j}xy^j$ are in $L$.)


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.