-2
$\begingroup$

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.

$\endgroup$
2
  • 3
    $\begingroup$ What do you have so far? $\endgroup$ – G. Bach Sep 15 '13 at 14:40
  • 4
    $\begingroup$ 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. $\endgroup$ – Raphael Sep 16 '13 at 8:22
2
$\begingroup$

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.

For an introduction to transductions see J. Berstel, Transductions and Context-Free Languages.

$\endgroup$
3
  • $\begingroup$ @J.-E. Pin plz post another solution other than not involving rational transduction function..bcoz i didn't know about rational transduction $\endgroup$ – Harshil Sep 15 '13 at 18:32
  • 3
    $\begingroup$ @user561298: Why should they? You did not show any effort, so be glad you receive any answer. It is not anybody's job to come up with an answer that will solve your homework. If you want an answer more suitable for your needs, you should elaborate your question. $\endgroup$ – Raphael Sep 16 '13 at 8:24
  • $\begingroup$ @Raphel..let me tell u it is not any homework problem..this question already appeared of my recently exams..i want to know the solution(eagerly) that's it!! $\endgroup$ – Harshil Sep 16 '13 at 13:00

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.