9
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Welcome! Where exactly are you stuck, what is your approach? $\endgroup$ – Raphael May 17 '12 at 16:30
  • 1
    $\begingroup$ Hint: think about how to best use non-determinism. $\endgroup$ – Artem Kaznatcheev May 17 '12 at 16:37
  • $\begingroup$ 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 right it down formally. $\endgroup$ – Dommicentl May 17 '12 at 17:53
  • 3
    $\begingroup$ I copied your comment into the question. That's a better place for it. $\endgroup$ – Dave Clarke May 17 '12 at 18:17
8
$\begingroup$

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.

$\endgroup$
6
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ Note that even what is in the spoiler areas is neither rigorous or formal. Please let me know if you need more detail (after having tried it yourself). $\endgroup$ – Raphael May 17 '12 at 19:39
6
$\begingroup$

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).

$\endgroup$
  • 1
    $\begingroup$ For what it's worth, the automata construction scales to other classes, too: at no point do we actually use that $A_L$ is a PDA. $\endgroup$ – Raphael May 17 '12 at 23:57
  • $\begingroup$ Good point.$ $ $ $ $\endgroup$ – sdcvvc May 18 '12 at 0:02
  • 1
    $\begingroup$ Technically such a class (where this proof works) is called a cone or full trio. $\endgroup$ – Hendrik Jan Jan 2 '13 at 1:27

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.