Deterministic context-free languages are not in general closed under substitutio

Question

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?

Explanation / Answer

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.

Related Questions

Navigate

• Browse (All)
• Browse D
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.