I'm stuck on the following question:

How to prove the linear context free languages are closed under gsm mapping?

  • 2
    $\begingroup$ It would help us if you explained what linear (or linear context free) languages are, and what are gsm mappings. $\endgroup$ Nov 2 '15 at 14:35
  • 1
    $\begingroup$ What are your thoughts? What approaches have you tried? $\endgroup$
    – D.W.
    Nov 2 '15 at 16:52
  • $\begingroup$ While "linear" is a standard notion in formal languages (cc @YuvalFilmus), "GSM mappings" is even ungoogleable. What is that? Also, what @D.W. said. $\endgroup$
    – Raphael
    Nov 2 '15 at 17:21
  • $\begingroup$ @Raphael A generalized sequential machine is basically a transducer. It's an NFA with a string on each of the non-$\epsilon$ transitions. $\endgroup$ Nov 2 '15 at 17:36

If you know that gsm mappings can be written as a composition of an inverse morphism, intersection with a regular language, and a morphism, then it suffices to observe that the linear languages are actually closed under these operations.


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.