New answers tagged automata-theory
2
After discussing it further with a3nm, I propose an algorithm that is
different than Neal's algorithm and works in a more general
setting. The approach gives polynomial delay algorithm but it uses
exponential space.
The only two properties that we will be using are :
(1) The problem is self-reducible, in the sense that if I am given an
automaton $A$ and $u \...
6
Here is a proposition for an elementary proof:
Let $\mathcal A=(A,Q,q_0,F,\delta)$ be a DFA for $L$, we want to build a DFA $\mathcal A'=(A,Q',q_0',F',\delta')$ for $f^{-1}(L)$. Intuitively, when reading a word $u$, $\mathcal A'$ will remember the state reached in $\mathcal A$ by $f(u)$, together with the action of $u$ on all states of $\mathcal A$. More ...
Top 50 recent answers are included
