Deterministic context-free languages are not in general closed under substitution. I have been looking at the DK-test (it is described in the 3rd edition of Sipser's Intro. to Theory of Computation, 2012) which can be used to check if a given CFG is deterministic, and it seems to me this can be used to show that DCFLs are closed under substitution when the substituted languages are disjoint DCFLs. Is this a known result? Or is anything known about the substitution closure of DCFLs with other restrictions on the substituted languages?


Since $ab$ is a DCFL, your result would imply that DCFLs are closed under concatenation, which they aren't. So your result can't hold.

  • $\begingroup$ Thanks. Still, it would only imply closure given the concatenated languages are disjoint, right? (I do see that it still would not hold). Do you have any idea about substitution with end-marked DCFLs, or end-marked & disjoint DCFLs? $\endgroup$ – sjmc Mar 10 '14 at 12:08
  • $\begingroup$ I'd guess that end-marked & disjoint alphabet should work. Disjoint languages with the same alphabet could get tricky, if the PDA can't decide early enough, which criteria it should test (cp. non-closure under union). $\endgroup$ – FrankW Mar 10 '14 at 12:17
  • $\begingroup$ Doesn't having disjoint alphabets have the same effect as end-markers? $\endgroup$ – sjmc Mar 10 '14 at 13:30
  • $\begingroup$ @sjmc Only if the word before substitution contains no substring $aa$ for any $a\in \Sigma$. $\endgroup$ – FrankW Mar 10 '14 at 14:22

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.