from w the letters in even-numbered positions; that is, if
w = a 1 a 2 a 3 a 4 …,
then
even (w)= a 2 a 4 .…
Corresponding to this, we can define a language
even (L) = {even (w): w ∈ L}.
Prove that if L is regular, so is even(L).
15. From a language L we create a new language chop2 (L)by removing the two
leftmost symbols of every string in L. Specifically,
chop2(L) = {w: vw ∈ L, with |v|= 2}.
Show that if L is regular, then chop2 (L) is also regular.
2.4 Reduction of the Number of States in Finite
Automata *
Any dfa defines a unique language, but the converse is not true. For a given
language, there are many dfa's that accept it. There may be a considerable
difference in the number of states of such equivalent automata. In terms of the
questions we have considered so far, all solutions are equally satisfactory, but if
the results are to be applied in a practical setting, there may be reasons for
preferring one over another.
Example 2.14
The two dfa's depicted in Figure 2.17(a) and 2.17(b) are equivalent, as a few test
strings will quickly reveal. We notice some obviously unnecessary features of
Figure 2.17(a). The state q 5 plays absolutely no role in the automaton since it can
never be reached from the initial state q 0 . Such a state is inaccessible, and it can
w = a 1 a 2 a 3 a 4 …,
then
even (w)= a 2 a 4 .…
Corresponding to this, we can define a language
even (L) = {even (w): w ∈ L}.
Prove that if L is regular, so is even(L).
15. From a language L we create a new language chop2 (L)by removing the two
leftmost symbols of every string in L. Specifically,
chop2(L) = {w: vw ∈ L, with |v|= 2}.
Show that if L is regular, then chop2 (L) is also regular.
2.4 Reduction of the Number of States in Finite
Automata *
Any dfa defines a unique language, but the converse is not true. For a given
language, there are many dfa's that accept it. There may be a considerable
difference in the number of states of such equivalent automata. In terms of the
questions we have considered so far, all solutions are equally satisfactory, but if
the results are to be applied in a practical setting, there may be reasons for
preferring one over another.
Example 2.14
The two dfa's depicted in Figure 2.17(a) and 2.17(b) are equivalent, as a few test
strings will quickly reveal. We notice some obviously unnecessary features of
Figure 2.17(a). The state q 5 plays absolutely no role in the automaton since it can
never be reached from the initial state q 0 . Such a state is inaccessible, and it can