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.

| cite | improve this answer | |

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.