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

3 Answers 3

9
$\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$
8
$\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$
2
  • $\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, 2012 at 19:39
  • $\begingroup$ don't we need to use the PDA to memorize states? for instance, we read w at reached state q_i at A_L , then how we actually simulate that we start from the state q_i after non-deterministaclly choosing some generated word constructed by the A_R? i was thinking that we need to push qi to the stuck them move to the starting state of A_R and guessing the next symbol according to its transition function, then pop from the stuck the previous state in the PDA put the current state in the NFA with the symbol we non deterministically choose and go back to the PDA making this move $\endgroup$
    – BOB123
    Jun 27, 2020 at 12:54
7
$\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$
3
  • 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, 2012 at 23:57
  • $\begingroup$ Good point.$ $ $ $ $\endgroup$
    – sdcvvc
    May 18, 2012 at 0:02
  • 2
    $\begingroup$ Technically such a class (where this proof works) is called a cone or full trio. $\endgroup$ Jan 2, 2013 at 1:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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