2
$\begingroup$

Knowing that $C$ is a context-free language and $R$ is a regular language, how to prove that $C / R = \{w| \exists x \in R: wx \in C\}$ is also a context-free language?

$\endgroup$
0
1
$\begingroup$

There is a simple proof uses PDAs. Start with a PDA for $C$. Add an $\epsilon$ transition to a copy of the PDA, multiplied by an NFA for $R$. Instead of reading characters from the input, this part guesses them and advances the NFA. The new machine accepts if both the PDA and the NFA accept. Details left to you.

$\endgroup$
2
$\begingroup$

Let me prove the following more general statement:

Every full trio is closed under right quotient by a regular language.

Let $\mathcal{L}$ be the full trio, let $L \in \mathcal{L}$ be a language over $\Sigma$, and let $R$ be a regular language over $\Sigma$. Let $\Sigma' = \{ \sigma' : \sigma \in \Sigma \}$. Define the homomorphism $h\colon \Sigma \cup \Sigma' \to \Sigma$ by $h(\sigma) = h(\sigma') = \sigma$, and define the homomorphism $k\colon \Sigma \cup \Sigma' \to \Sigma$ by $k(\sigma') = \sigma$, $k(\sigma) = \epsilon$. Then $$ L/R = k(h^{-1}(L) \cap \Sigma^{\prime *} R). $$

$\endgroup$
4
  • $\begingroup$ is it possible to prove it using simple things like PDA or NFA?? $\endgroup$ – Fatemeh Karimi May 11 '18 at 15:49
  • 1
    $\begingroup$ Closure under quotient with a regular language is a very standard closure property, so if you browse through textbooks, you will probably find several different proofs. I'm not immediately sure how a prove using context-free grammars would work, but a prove using PDAs is quite straightforward, and makes a nice exercise. $\endgroup$ – Yuval Filmus May 11 '18 at 16:02
  • $\begingroup$ is it valid to connect a PDA to an NFA?? because first I thought that if I connect the accept state of the PDA to the start state of NFA, and change the labels on the NFA a bit(adding an epsilon indicating top of the stack (making the transitions similar to the PDA for example ($a, \varepsilon -> \varepsilon$) this will solve the problem. but I doubt about it. is it ok to do so?? $\endgroup$ – Fatemeh Karimi May 11 '18 at 16:07
  • 1
    $\begingroup$ I'm assuming this is a comment on the other answer. In the end, you have to come up with an honest-to-god PDA. This PDA starts by simulating the original PDA, and then nondeterministically continues to simulate the PDA but now also simulates the NFA, and furthermore starts guessing the input rather than reading it. All of this can be implemented using a PDA, and it's a good exercise to work it out. $\endgroup$ – Yuval Filmus May 11 '18 at 16:30

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