3
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Note that this is not concatenation but right-quotient. $\endgroup$ – Raphael Jan 30 '14 at 11:02
6
$\begingroup$

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_X\times 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 $X\times 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.

$\endgroup$
  • $\begingroup$ I followed Phase 1, and I think I am beginning to understand Phase 2. The part that I'm not sure I understand is 1) How guessing the word $x$ would work (an $\epsilon$ transition?), and 2) how the PDA ($Z$) could know that it has reached an accept state in both automata simultaneously. $\endgroup$ – therealrootuser Jan 30 '14 at 3:56
  • $\begingroup$ for guessing the word $x$, you just guess letter by letter, and advance simultenously in both automata $X$ and $Y$ according to the letter you guessed. For instance if you are in state $(p,q)$, you guess letter $a$, you go to state $(p',q')$ (and update the stack of $X$ accordingly) such that transitions in both automata are valid. A state $(p,q)$ is accepting if $p$ is accepting in $X$ and $q$ is accepting in $Y$. $\endgroup$ – Denis Jan 30 '14 at 13:38
4
$\begingroup$

Here is a very short proof relying on rational transductions. Let $X$ be the alphabet. First the relation $\tau$ defined by $\tau(u) = uB$ is a rational transduction. Indeed its graph $(\Sigma_{x \in X} (x,x))^*(\{1\} \times B)$ is a rational subset of $X^* \times X^*$. This is the place where the hypothesis that $B$ is regular is mandatory. Now $$ A/B = \{u \mid \tau(u) \cap A \not= \emptyset \} = \tau^{-1}(A) $$ where $\tau^{-1}$ denotes the inverse of the relation $\tau$, which is also a rational transduction. Finally, it suffices to use the fact that if $L$ is context-free and $\sigma$ is a rational transduction, then $\sigma(L)$ is context-free.

$\endgroup$
0
$\begingroup$

Above answers are excellently written. But one other approach would be helpful I think.

We want to prove that if $L(A)$ is a $CFL$ and $L(B)$ is a regular then $L(A/B) = \{w\space|\space wx \in A,\space x\in B,\space w\in \Sigma^*\, ,\space x\in \Sigma^*\}$ is also a $CFL$.

Let's use fact that set of regular languages and set of context free languages are closed under homomorphism and inverse homomorphism.

Let's define $\overline\Sigma^* = \{\overline a\space|\space a\in\Sigma\}$

Now define homomorphism

$unbar:\space (\Sigma\space \cup \overline\Sigma)^* \rightarrow \Sigma^*$

$unbar(a) = a, \space \space if\space a\in \Sigma$

$unbar(\overline a) = a, \space \space if\space a\in \overline\Sigma$

and

$rembar:\space (\Sigma\space \cup \overline\Sigma)^* \rightarrow \Sigma^*$

$rembar(a) = a, \space \space if\space a\in \Sigma$

$rembar(\overline a) = \epsilon, \space \space if\space a\in \overline\Sigma$

Now, proof

$L_1 = unbar^{-1}(A)$

L_1 is CFL because A is CFL and CFL is closed under inverse homomorphism.
L_1 is set of strings in A with arbitrary letter annotated with bars.

$L_2 = unbar^{-1}(B)$

L_2 is a regular because regular set is also closed under inverse homomorphism.
Meaning of L_2 is similar to above.

$L_3 = L_2\space\cap\space\overline\Sigma^* $

Now L_3 is also regular because L_2 is regular and regular set is closed under intersection. 
L_3 is set of strings in B with every letter annotated with bar.

$L_4 = \Sigma^*L_3$

This too is regular.

$L_4$ is set of strings of form $xy, x\in \Sigma^*$ and $y$ is string in B with every letter annotated by bar.

$L(A/B) = rembar(L_1 \space\cap\space L_4)$

Now this is CFL because L_1 is CFL and L_4 is regular and CFL is closed under regular 
intersections.

Now this is little hard to explain but you may infer the meaning.

Inshort, $L(A/B) = rembar(unbar^{-1}(A) \space\cap\space (\Sigma^*(unbar^{-1}(B)\space\cap\overline\Sigma^*)))$

All operations used preserve Context-free-ness so L(A/B) is CFL.
$\endgroup$

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.