snippetMinor
How to build a deterministic finite automaton from a given one with a new definition for automaton language?
Viewed 0 times
definitionfinitenewwithgivenlanguageonedeterministicforhow
Problem
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:
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:
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
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
Solution
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.
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.
Context
StackExchange Computer Science Q#150038, answer score: 4
Revisions (0)
No revisions yet.