# How to find a push-down automata that describes $f_{\sigma}(L)$? (given that $L$ is context free language)

Let it be $L$ a context free language. Definition:
$f_{\sigma}(L)$={$w:σw∈$$L$}.

Need to find a push-down automata $M'$ so that $f_{\sigma}(L)$=$L(M')$.

Ok, so here is my idea for solution, but I am not sure if I am correct here, so please fix me if I am wrong:
We know that we have push-down automata $M=(Q,∑,Γ,∆,s,A)$ so that $L=L(M)$.
Now we will define $M'=(Q',∑,Γ',∆',s',A')$ like this:

* was edited from this part (I had the wrong answer before+didn't explain it well. now I will fix this) *

First, we will define the function $E$ for an automata $M$ and a state $q$:
$E(q)$={$p∈Q:(q,ϵ,γ)↦(p,ϵ,γ)$}
(the group of states you can get starting from $q$ and doing epsilon transitions only).
and now: $Q'=Q∪${$q':q∈E(s)$}$,Γ'=Γ,A'=A$
and for the transition function:
let it be $q_i∈Q$.
case $q_i∈E(s)$: if $∆(q_i,σ,γ)=(q_{i+1},γ')$ then $∆'(q_i',ϵ,γ)=(q_{i+1},γ')$
if $∆(q_i,ϵ,γ)=(q_{i+1},γ')$ then $∆'(q_i',ϵ,γ)=(q_{i+1}',γ')$
case $q_i∉E(s)$: ∆'=∆

Explain about the automata: for every reading of prefix $\sigma$ at $M$, we defined that at $M'$ the empty word will be readen, and after the reading of this letter- $M'$ will act just like $M$. note that reading prefix $\sigma$ at $M$ can be performed by more then one transition, in case we have epsilon transitions from $s$. for a case like this, we saved a paralel states for each $q∈E(s)$, with transitions that act the same as in $M$.

Is this automata indeed describes $f_{\sigma}(L)$?

• Explain what you want your transitions to accomplish. Just giving them leaves us guessing. Commented Jan 1, 2016 at 15:51
• Edited now. added an explanation+changed the answer Commented Jan 2, 2016 at 0:30