2
$\begingroup$

If I have a DCFG G for some language over {0,1}* and a DCFG H for its complement, with disjoint non-terminals, and a (perhaps partially reduced) string, can they both have a handle for the string? So the right hand sides of these rules would consist of only terminals and one would be a (maybe proper) prefix of the other. I think it's possible but I'm not certain and can't quite show it.

$\endgroup$
1
$\begingroup$

What you want is not necessarily possible. So you have to build grammars that will make it possible.

Try prefixing both languages by $\{0,1\}^3$ (for example). That is, if $L_G$ and $L_H$ are the languages corresponding to your grammars, consider the languages $\{0,1\}^3$.$L_G$ and $\{0,1\}^3$.$L_H$.

You should be able to build grammars for them, and also prove that they are complement of each other. You should also be able to show that since, there are DPDAs recognizing the two languages $L_G$ and $L_H$, you can build from them DPDAs that recognize your augmented languages.

If you build the grammars as you should (it is very easy), you will get your double handle.

The only problem is that, since both handles are on the same side, you cannot use them for a bicycle, or for a heavy pot.

$\endgroup$
  • $\begingroup$ Thanks for the reply, good to see it is at least possible. I should have mentioned, I'm specifically looking at permutation-invariant languages (ex. "more 1's than 0's"), if that makes a difference for showing it's (im)possible using the unmodified languages. $\endgroup$ – sjmc Mar 19 '14 at 10:06
  • $\begingroup$ @sjmc That seems a strange problem you are working on. Clearly, my suggestion does not preserve the permutation invariant property. Permutation closure will add many other strings to each language in general, and they will not remain complements of each other. $\endgroup$ – babou Mar 19 '14 at 16:57
  • $\begingroup$ Yeah,but I think I've determined it's possible, at least on the very first step of the derivation. Any long enough string should have a forced handle in both G and its complement (this handle will either be variable -> epsilon or variable -> terminals, since the string is not even partially reduced). The string just has to be long enough that it's not immediately obvious which language it belongs to. Suppose it's 10101010101010101. Obviously this has a forced handle in "more 1s than 0s".Add another 0 and it's in the complement, but this 0 doesn't figure in the first reduction anyway. $\endgroup$ – sjmc Mar 20 '14 at 8:06

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.