2.7 Minimum Deterministic Finite Automata 79
Exercise 2.7
- Find all equivalence classess of RL for the following languages:
(a) (0 + l)*Ol(O + l)*.
(b) (00 + ll)(O + 1)“.
(c) Oll(0 + l)*ool.
(d) The set of binary strings in which each block of four symbols have
at least two 0’s.
(e) {z E {O,l}* 1 #O(X) = #l(z)}, where Sjta(w) is the number of
occurrences of symbol a in w.- For each of the following languages L, show that Index(L) = 00 and so
L is not regular.
(a) {Omln IO < m. < n}.
(b) {OYmO”+m 1 n;m > 0).
(c) {ww 1 w E {o,1}*}Y
(d) {X@W ( x, w E {O,l}+}. - For each of the following languages L, show that no two strings can be
in the same equivalence class of RL.
(a) {OP I p is a prime}.
(b) {On2 I n > 0). - - Construct the minimum DFA’s for languages accepted by DFA’s in Fig-
ure 2.52(a) and 2.52(b).
Figure 2.52: Two DFA’s for Exercise 4.- Construct a minimum DFA equivalent to the NFA of Figure 2.53.