How to build a deterministic finite automaton from a given one with a new definition for automaton language?

Question

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:

1. keep the base of automaton $A$, the path to each accepting state remains the same
2. 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:

1. for each state in $A$ have another copy of it in $B$
2. for each of the states in the first copy of $A$ define the transition function the same way as $A$
3. 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?

Answer 1

Your second construction seems to work well.

This can be formalized by starting with the formal definion of an automaton and specifying the components of the new one. So for $\mathcal A=(Q,\Sigma,\delta,q_{in},F)$ construct a new automaton $\mathcal A'=(Q',\Sigma,\delta',q'_{in},F')$.

The state set $Q'$ consists of two copies of the original one, this can be implemented by a cartesian product $Q' = Q\times \{1,2\}$. States $(q,1)$ and $(q,2)$ are the new copies of original $q\in Q$. To start with, the new initial state equals $q'_{in} = (q_{in},1)$. Final states are in $F'= F\times\{2\}$. The transition relation consists of two types of transitions: either following the original relation in one of the copies, or moving to the second copy.

If intuition is not sufficent to convince the construction works, you can find a matching between computations of the two automata. They are essentiallly equal, except for the component-index.

Answer 2

You have described your "new algorithm" pretty clearly.

A formal description

The formal way to describe it would be something like the following. We will use the formal definition of deterministic finite automaton (DFA)

Input: a DFA $A=(Q,\Sigma, \delta, q0, F)$
Output: another DFA
Procedure:

1. Let $Q'=Q\times\{\text{false},\text{true}\} $ .
2. Define $\delta'$ such that for all $q\in Q$ and all $\sigma\in\Sigma$,
   • $\delta'((q,\text{false}), \sigma)= \begin{cases} (\delta(q, \sigma),\text{true})\ \text{ if }q\in F\\ (\delta(q, \sigma),\text{false})\ \text{ if }q\not\in F \end{cases}$
   • $\delta'((q,\text{true}), \sigma)=(\delta(q, \sigma),\text{true})$
3. Let $F'=\{(f,\text{true})\mid f\in F\}$
4. Return DFA $A'=(Q',\Sigma, \delta', (q0,\text{false}), F')$.

A proof that is good enough

It is easy to check that

• if the second component of each state in $A'$ is ignored, the transitions of $A'$ is exactly the same as that of $A$.
• the second component of each state in $A'$ tracks whether the first component has been to an accept state of $A$ during the previous transitions.

Since

• the second component of the initial state of $A'$ assumes no previous transitions to an accept state of $A$ by the first component,
• a state of $A'$ is an accept state iff
  • its first component is an accept state of $A$ and
  • its second component means the first component has been to an accept state of $A$ during the previous transitions,

the language accepted by $A'$ is exactly the language accepted by $A$ by the "new definition".

More formal proofs

To make the proof more formal, we should prove each of following separately, using detailed analysis of the transitions made by $A$ and $A'$ on an arbitrary input string $s$.

• if $s$ is accepted by $A$ by the "new definition", $s$ will be accepted by $A'$
• if $s$ is accepted by $A'$, $s$ will be accepted by $A$ by the "new definition".

To make the proof even more formal, we could use some formal proof system such as HOL Light, Isabelle, Coq, etc. However, that is way beyond the usual course of learning DFA.