If $L$ is context-free and $R$ is regular, then $L / R$ is context-free?

Question

I'm am stuck solving the next exercise:

Argue that if $L$ is context-free and $R$ is regular, then $L / R = \{ w \mid \exists x \in R \;\text{s.t}\; wx \in L\} $ (i.e. the right quotient) is context-free.

I know that there should exist a PDA that accepts $L$ and a DFA that accepts $R$. I'm now trying to combine these automata to a PDA that accepts the right quotient. If I can build that I proved that $L/R$ is context-free. But I'm stuck building this PDA.

This is how far I've made it:

In the combined PDA the states are a cartesian product of the states of the seperate automata. And the edges are the edges of the DFA but only the ones for which in the future a final state of the original PDA of L can be reached. But don't know how to write it down formally.

Answer 1

Here is a hint.

You need your machine to initially accept part of a word from $L$, consuming the tape as it goes. Then, without consuming anything, you need to find some word from $R$ that will push the machine into a final state. The chosen word from $R$ plays the role of the input word for the second half of the computation.

Clearly, non-determinism will have a role, as will the product between the two machines. The trick in formalising this is adjusting the product to deal with the fact that the input comes from $R$ not from the input.

Answer 2

I am not sure what you are getting at with the cartesian product; this simulates both automata in parallel, which will give you the intersection. But you want it to identify all words in $L$ that have a suffix from $R$! On an intuitive level, that is.

Assume our input is $w \in \Sigma^*$. Obviously, we can not check all possible continuations (for membership in $R$) but only a finite number of them. Artem's comment is most helpful here; we guess what the suffix $x$ is going to be, and run both automata on it.

Let $A_L$ and $A_R$ the PDA for $L$ and NFA for $R$, respectively. Construct an automaton $A$ as follows. On input $w \in \Sigma^*$, simulate $A_L$. After $w$ is consumed, switch to a modified intersection $A_{L,R}$ of $A_L$ and $A_R$, keeping the state from $A_L$. Now, decide for every transition nondeterministically which symbol is next in the virtual input. Accept $w$ if and only if both components of $A_{L,R}$ reach a final state simultaneously, that is if $w$ has a continuation $x$ so that $wx \in L$ and $x \in R$.

You can also use formal grammars. Do you see how you can derive in two grammars in parallel? In general, it is not clear how to adapt $G_L$ so you get a handle on suffixes; using the Chomsky normal form helps.

Assume both $G_L$ and $G_R$ are given in Chomsky normal form. Modify $G_L$ such that the right-most non-terminal is distinguishable and make its start symbol the new start symbol. Introduce for the distinguished versions of the nonterminals new rules that lead to a grammar that derives in $G_L$ and $G_R$ in parallel (non-terminals are pairs of non-terminals); if both grammars agree on a terminal symbol, delete the composite non-terminal. That way, a suffix in $G_L$ is deleted if and only if it can be derived in $G_L$ and in $G_R$, it remains $w \in L/R$.

Answer 3

I recommend to use Raphael's answer, which is much easier to understand, but here is an alternative one, using closure properties instead of automata:

Let $L \subseteq A^{\ast}$ be a language. We want to read a word $w$, but ask $L$ whether $w x$ is in the language. So we want to create a new language from $L$ which has $x$ "erased". We can do it using a homomorphism, but it could remove letters from $w$. Solution: split the alphabet into two and use different letters for $w$ and $x$.

More formally:

1) Create $L' \subseteq (A \times \{0,1\})^{\ast}$ of words from $L$, with each letter tagged either 0 or 1.
2) Intersect it with regular language $(A \times {0})^{\ast} (R \times 1)$. This forces that all 0's come before all 1's, and the second part comes from $R$. The precise meaning of $\times$ is left for the reader.
3) Substitute $(a,0) \to a$ and $(a,1) \to \varepsilon$.

Used closure properties: Homomorphic image, preimage, intersection with regular languages. Advantage: This proof works for other families (for example, replace context-free with regular).