Let $A$ be a nondeterministic automaton. Let $X(A)$ the set of words for which there at least two accepting paths.
In one of the previous exam, for which no answers are available, it is required to prove that there exist a deterministic automaton whose language is $X(A)$. Furthermore, if the original automaton has $k$ states, then the new automaton should have $3^k$ states.
I have tried multiples approaches to no avail:
- Make an automata that keeps track of which path was taken, but the size of the automata grew infinitely because of cycles...
- An automaton for each state I also kept track of which state it came from, but it was just a scaled down version of previous attempt. Which didn't work if the path started to converge early.
- Tried an automaton where I encoded each state with the set of all the states from automaton $A$. And for each state I included whether I went through that state 0, 1 or more than 2 times.