Let it be $L$ a context free language. Definition:
\(\displaystyle f_{\sigma}(L)={w:σw∈L}\).
Need to find a push-down automata M' so that \(\displaystyle 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:
First, we will define the function E for an automata M and a state q:
E(q)={p∈Q|(q,ϵ,γ)\(\displaystyle ↦^*\)(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 \(\displaystyle q_i∈Q\).
case \(\displaystyle q_i∈E(s): if ∆(q_i,σ,γ)=(q_{i+1},γ') then ∆'(q_i',ϵ,γ)=(q_{i+1},γ')\)
if \(\displaystyle ∆(q_i,ϵ,γ)=(q_{i+1},γ') then ∆'(q_i',ϵ,γ)=(q_{i+1}',γ')\)
case \(\displaystyle q_i∉E(s)\): ∆'=∆
Explain about the automata: for every reading of prefix \(\displaystyle \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 \(\displaystyle \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 \(\displaystyle f_{\sigma}(L)\)?
\(\displaystyle f_{\sigma}(L)={w:σw∈L}\).
Need to find a push-down automata M' so that \(\displaystyle 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:
First, we will define the function E for an automata M and a state q:
E(q)={p∈Q|(q,ϵ,γ)\(\displaystyle ↦^*\)(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 \(\displaystyle q_i∈Q\).
case \(\displaystyle q_i∈E(s): if ∆(q_i,σ,γ)=(q_{i+1},γ') then ∆'(q_i',ϵ,γ)=(q_{i+1},γ')\)
if \(\displaystyle ∆(q_i,ϵ,γ)=(q_{i+1},γ') then ∆'(q_i',ϵ,γ)=(q_{i+1}',γ')\)
case \(\displaystyle q_i∉E(s)\): ∆'=∆
Explain about the automata: for every reading of prefix \(\displaystyle \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 \(\displaystyle \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 \(\displaystyle f_{\sigma}(L)\)?