# CFL and inverse homomorphism

I found a proof that shows CFL is closed under inverse homomorphism.

First of all the Definition of an homomorphism and its inverse:

$h: \Sigma^{*} \rightarrow \Delta^{*} \ \ \ h(L) = \{h(w) |w \in L\}$

$h^{-1}: \Delta^{*} \rightarrow \Sigma^{*} \ \ \ h^{-1}(L) = \{w | h(w) \in L\}$

The proof I found works as follows:

Let $L = L(A)$ for some PDA $A$. Construct PDA $A’$ to accept $h^{-1}(L)$. $A’$ simulates $A$, but keeps, as one component of a two-component state a buffer that holds the result of applying $h$ to one input symbol.

I really can't get my head around that intuition. My approach was to create an example:

Let $L=\{a^{n}b^{n} | n \in \mathbb N\}$ and $h: \{a,b\}^{*} \rightarrow \{0,1\}^{*} | \ \ h(a) = 01, h(b) = 1$

$\Rightarrow h(L)= \{(01)^{n}1^{n} | n \in \mathbb N\}$

I would then create an PDA $A$ that accepts my $h(L)$ and PDA $A'$ (because I already know how my inverse image looks like) that accepts $L$.

And that is the point I got stuck. I know that I need a different PDA for $A'$ with some sort of buffer but I don't know how to realise that.

My Question: Can someone explain the proof a little bit more detailed. And what it means that $A'$ simulates $A$?

Suppose that $A=(Q,\Delta, \Gamma, \delta, q_0, \gamma_0, F)$.

Define $\operatorname{Prefs}(u)$ to be the set $\{v|\exists w, u = vw\}$ of prefixes of $u$.

Define $A':=(Q',\Sigma, \Gamma, \delta', q_0', \gamma_0, F')$ by:

• $\displaystyle Q':= \left(Q\times \left(\bigcup_{a\in \Sigma}\operatorname{Prefs}(h(a))\right)\right) \sqcup \left(Q\times \Sigma \right)$. A state $(q,u)$ with $u\in\operatorname{Prefs}(h(a))$ will mean "I'm in state $q$ in $A$, I've read $u$ and am waiting for the rest of $h(a)$ and then I'll go to $(q,a)$" while a state $(q,a)$ means "I've read $h(a)$ and will now simulate a transition reading $a$ in state $q$ in $A$ to arrive to some state $(q',\varepsilon)$".

• Transitions are (where if a transition doesn't mention the stack, it means it doesn't change it):

• $(q,u)\overset{b}{\to}(q,ub)$ whenever the destination state exists (i.e. if you can read the letter while remaining a prefix of some $h(a)$, you can just keep reading)

• $(q,h(a))\overset{\varepsilon}{\to}(q,a)$ (i.e. at any point, if the word I've read is the image of a letter by $h$, I can replace it by its preimage)

• $(q,a)\overset{\varepsilon,...}{\to}(q',\varepsilon)$ whenever $q\overset{a,...}{\to}q'$ in $A$ (where both $...$ are the same thing) (i.e. if I just read the image of $a$, simulate reading $a$ in $A$)

• $q_0':=(q_0,\varepsilon)$

• $F':=F\times \{\varepsilon\}$

Then (I think that) $L(A')=h^{-1}(L(A))$.

What you call "buffer" would be the right component of the states used to remember the prefix of $h(a)$ you've read.