Let it be $L$ a context free language. Definition:

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$:
(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)$?

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


You must log in to answer this question.

Browse other questions tagged .