I was given a new definition for a language of an automaton.
A word is part of the automaton language if and only if the automaton finished on an accepting state and it was in an accepting state at least once before
Note: it doesn't have to be the same accepting state.
Now given a deterministic finite automaton $A$ that has a language according to the new definition, I need to find an algorithm to build a new deterministic finite automaton $B$ that has the same language but according to the default definition of a language, i.e. a word is part of the language if and only if the automaton has finished in an accepting state.
The algorithm I came up with is this:
- keep the base of automaton $A$, the path to each accepting state remains the same
- for each of $A$'s accepting state, remove it from the accepting states, and attach another $A$ automaton to it where it will be the initial state.
so if $A$ has $n$ accepting states I need $n + 1$ $A$ automata to build automaton $B$ which will have $n ^ 2$ accepting states. while this algorithm seems to be working I'm having a problem to formally describe it and show that it is indeed the same language. Moreover this seems unnecessarily complex and wasteful with so many accepting states, I don't think there should be more then $n$ accepting states in $B$ as well.
Therefore I came up with a new algorithm:
- for each state in $A$ have another copy of it in $B$
- for each of the states in the first copy of $A$ define the transition function the same way as $A$
- for each of the accepting states in the first copy of $A$, first remove them from the accepting states set, then update the transition function so that using the second copy of all the states of $A$ there is a path from each formerly accepting state to the new accepting states as if it was the initial state.
The second algorithm seems to me to be a much better candidate as it uses only $2n$ states and thus a much simpler transition function is needed, but yet again I've hit the brick wall which is describing this algorithm formally and showing the equality between the language of the new $B$ automaton and $A$'s language.
How can I show this equality? and how should I describe the algorithm so it will be formally acceptable?