# Tag Info

## Hot answers tagged automata

### Is the reversal of a minimal DFA also minimal?

The "standard" example that shows that the NFA to DFA construction is exponential in size also works for reversal. The DFA for $\{0,1\}^*1\{0,1\}^n$, the $n+1$-st symbol from the right is $1$...
• 28.2k

### Can an algorithm decide whether any DFA accepts an infinite language? What is its time complexity?

In addition to the answers linked by Rinkesh P. in a comment, here is an approach that directly translates into an efficient algorithm. The DFA accept an infinite language if and only if there is a ...
• 24.5k

### How to convert the regular expression $\emptyset^*$ to an NFA?

That's not a phi symbol (phi is written either $\phi$ or $\varphi$, and the uppercase version is $\Phi$), but you are right that $\emptyset$ denotes the empty set. The star symbol is known as the ...
• 24.5k
Seems mimimal to me. You can actually prove that the DFA is minimal by applying the Myhill-Nerode theorem. Two states $p$ and $q$ can not be merged if they can be "distinguished" in the ...