Which state minimization algorithm runs in O(n log n) time for DFAs?
Hopcroft's algorithm minimizes a DFA with n states in O(n log n) time using partition refinement.
For a language L over {0, 1}, let L = {$0^n$ $1^m$ | n >= m >= 0}. Language L is:
The language is context-free because a PDA can push for each a and pop for each b while checking that the number of b's does not exceed the number of a's. It is not regular by the pumping lemma.
If L is a regular language, then the language REVERSE(L) = {$w^R$ | w in L} is:
Regular languages are closed under reversal (reversing NFA transition directions and swapping start/final states gives an NFA for $L^R)$.
How many states are in the minimal DFA accepting $L = {w$ in {0,1}* | number of 0s in w is even AND number of 1s in w is odd}?
Cross-product DFA of two 2-state DFAs (parity of 0s and parity of 1s) requires 2 x 2 = 4 states.
The language L = {$a^n$ $b^n$ | n <= 10^6} is:
Any finite language is regular, regardless of how large the finite bound is.