Closure of CFL against right-quotient with regular languages

ignougroup
Problem Detail: 

Let $A/B$ = ${ w mid wx in A$ for some $x in B }$. Show that if A is context free and B is regular, then $A/B$ is context free.

My interpretation of this is is that we need to show that if a string $wx$ is accepted by a CFG, and we know that $x$ is accepted by a regular language (and therefore is also accepted by a context-free language), then $w$ must also be accepted by a CFG. My initial thought on how to solve this would be a proof by contradiction in which we assume that $A$ is context free, $B$ is regular, and then assume that $A/B$ is not context-free. Since $A$ is context free, we can construct an equivalent PDA that accepts $A$. From here, my thought was to take an arbitrary $wx$ that is accepted by $A$, such that $x in B$. We can then construct another PDA based on the first that only accepts $wx$. We could then break the PDA into two pieces: one that accepts $w$ and one that accepts $x$ (with the two pieces concatenated together). Since there then would exist a PDA that accepts just $w$, and $w$ is arbitrary insofar as $wx$ was arbitrary, $A/B$ must therefore be context-free after all (contradiction). Will this approach work? (Is this a good general approach?) If so, how would I go about breaking the PDA that accepts $wx$ into chunks formally?

Asked By : mattingly890

Answered By : Denis

Imagine you have a pushdown automaton (PDA) $X$ for $A$ and a DFA $Y$ for $B$. You want to build a PDA $Z$ for $A/B$. You can do as follows: the states $Q_Z$ of $Z$ are $Q_Xtimes Q_Y$. There are two phases: Phase 1: You just read the input word and advance in $X$, states of $Y$ are ignored. This corresponds to the word $w$ of your language. Phase 2: When you reach the end of $w$, you are allowed to perform $epsilon$-transitions in order to reach an accepting state of $Xtimes Y$. So you guess a word $x$ that will continue to advance in $X$ and start to advance in $Y$, and that has to reach acceptance in both automata simultaneously. If there is an accepting run of this automaton, then the input word $w$ is in $A/B$ since you guessed the witness $x$ (and vice-versa, if $x$ exists, then it can be guessed by your automaton $Z$). The reason why $B$ has to be regular instead of CFL is that you cannot manage two stacks at the same time, if you want to stay CFL.
Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/20090