A homomorphism on an alphabet is a function that gives a string for each symbol in that alphabet – for example, a homomorphism h on the binary alphabet might be defined so that h(0) = ba and h(1) =...

See Image.

Extracted text: A homomorphism on an alphabet is a function that gives a string for each symbol in that alphabet – for example, a homomorphism h on the binary alphabet might be defined so that h(0) = ba and h(1) = edc. Homomorphisms can be extended to strings and languages in the straightforward way: If s = s,5253.S, then h(s) = h(s1) h(s2) h(s)... h(s„). If L is a language then h(L) = { h(s) | s is in L }. Show that the class of context free languages is closed under homomorphism – that is, that for any context free language L, and any homomorphism h on its alphabet, h(L) defined as above is context free. HINT: If your proof is very long, you are doing more than you need to.