I saw from different sources that Context Free Grammars are insufficient to generate cross serial dependencies (interleaving) in languages and it would require mildly context sensitive grammars to do that. So if mildly context sensitive grammars can handle them I guess it must follow from that context sensitive grammars can handle them too. I am not familiar with mildly context sensitive grammars and was trying to implement interleaving with the more powerful context sensitive grammars (αAβ → αγβ).

I have been trying to figure out how just by having context preserving rules (αAβ → αγβ) enable us to interleave elements. Can someone provide a simple set of context sensitive rules that allows cross serial dependency (ex: a1b1a2b2)?

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.