I'm trying to work out a proof by construction that $L/a$ would be regular.

$a$ is any final symbol at the end of an accepted string, so I figured the only part of the machine that would have to be changed is the set of accepted states ($F$)

I came up with the following definition of $F'$ for the new

$F' = \{q ∈ Q | \delta(q, a) ∈ F\}$

Where $Q$ is the set of states (the same for both machines), and $\delta$ is the transition function (also the same for both machines). I believe this would make any state that has a transition to an accepting state in the first machine an accepting state in the second machine (including prior accepting states, if they have a self-loop).

Am I missing anything here? It seems suspicious to me that I would only need to modify the set of accepting states and not any other component.

  • $\begingroup$ Well, have you tried it on some examples to see if it seems to be correct on those examples? Have you tried to prove your answer correct? Those would be the usual first strategies to check your answer. $\endgroup$ – D.W. Sep 21 at 17:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.