3 votes

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
2 votes

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
2 votes

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
2 votes
Accepted

Is my DFA optimal?

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 ...
  • 28.2k

Only top scored, non community-wiki answers of a minimum length are eligible