0
$\begingroup$

Suppose we have PDA (same for DFA and Turing) that has a transition from a state to itself. Can we convert this PDA to another one without any transition like this?

EDIT (My thoughts):
I guess we can do it. for example in a PDA enter image description here we might be able to do this(?)

Improve this question
$\endgroup$
2
  • $\begingroup$ What do you think and why? $\endgroup$
    – Steven
    Commented Jun 30, 2021 at 7:54
  • $\begingroup$ @Steven I've edited the question $\endgroup$
    – Kurosh Ghanizadeh
    Commented Jun 30, 2021 at 8:07

1 Answer 1

Reset to default
1
$\begingroup$

If you replace the $\epsilon$'s with $a$'s then what you did is a possible solution (that is, cloning the transition from $q_0$ to itself into two identical transitions: $q_0\rightarrow q_1$ and $q_1\rightarrow q_0)$. however, notice that any transition from $q_0$ must also be duplicated to be a transition from $q_1$. In addition, don't forget to make the duplicated state an accepting state if the original was an accepting state

So, doing this while cloning all transitions and other properties, will ensure that the DFA/PDA/TM will be equivalent.

Notice that in the special case of TM the accepting state will never be duplicated, since it doesn't have any transitions at all.

Improve this answer
$\endgroup$
2
  • $\begingroup$ If I exchange ϵ 's with a's then I must read 2 "a" from input and it'll not be the same output $\endgroup$
    – Kurosh Ghanizadeh
    Commented Jun 30, 2021 at 8:50
  • $\begingroup$ Hence you need to duplicate all transitions that were from $q_0$ to also be in $q_1$. $\endgroup$
    – nir shahar
    Commented Jun 30, 2021 at 8:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.