# Prove that X/Y/Z is context-free

Given languages X, Y and Z, each with alphabet, define X/Y/Z as:

     X/Y/Z = { w ∈ Σ* | ∃u ∈ Y and ∃v ∈ Z; such that wuv ∈ X }.


Prove that if X is context-free, and Y and Z are regular, then X/Y/Z is context-free.

• What do you have so far? – G. Bach Sep 15 '13 at 14:40
• This is a pure exercise dump. What have you tried? Where did you get stuck? See here for a discussion why we think your question is bad, and here for questions you should check out before asking. Once you include your own attempts, you have posted a question in its own right that can be answered to solve your specific problem. – Raphael Sep 16 '13 at 8:22

Setting $T = YZ$, your language is the set $L$ of all $w \in \Sigma^*$ for which there is a $t \in T$ such that $wt \in X$. In other words, $L$ is the right quotient of $X$ by $T$. Now, if $X$ is regular, so is $L$ (in all cases) and if $X$ is context-free and $Y$ and $Z$ are regular, then $T$ is regular and $L$ is context-free. One way to prove this latter statement is to consider the rational transduction $\tau$ defined by $\tau(u) = uT$ and observe that $L = \tau^{-1}(X)$. Now, the inverse of a rational transduction is also a rational transduction and context-free languages are preserved under rational transductions.