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

I'm stuck on the following question:

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

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

1 Answer

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.