What is the equivalent regular expression for the DFA transitions: $\delta(q0, 0)=q1, \delta(q1, 0)=q0, \delta(q0,1)=q0, \delta(q1,1)=q1$ with start q0 and final q0?
q0 maintains an even number of 0s with any number of 1s interleaved. Expression: 1*(0 1* 0 1*)*.
Which of the following operations does NOT preserve regularity of languages?
Regular languages are closed under finite union, but NOT infinite union (e.g., infinite union of singletons {$a^n$ $b^n}$ yields non-regular {$a^n$ $b^n$ | n >= 0}).
In Myhill-Nerode theorem, a language L is regular if and only if the number of equivalence classes of its right-invariant congruence relation is:
Myhill-Nerode theorem states L is regular iff the index (number of equivalence classes) of $R_L$ is finite, which equals minimal DFA states.
If NFA N has 5 states, the maximum number of states in an equivalent minimal DFA is:
Subset construction can yield up to $2^n$ states. For $n = 5$, max states = $2^5$ = 32.
Which algorithm converts a regular expression into an $\epsilon-NFA$?
Thompson's construction recursively builds an $\epsilon-NFA$ from a regular expression in linear time.