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