11. Rework Example 3.11, this time eliminating the state OO first.
12. Show how all the labels in Figure 3.14 were obtained.
13. Find a regular expression for the following languages on {a, b}.
(a) L = {w : n a (w) and n b (w) are both even}.
(b) L = {w :(n a (w) - n b (w)) mod 3 = 1}.
(c) L = {w :(n a (w) - n b (w)) mod 3 = 0}.
(d) L = {w :2n a (w)+3n b (w)is even}.
14. Prove that the construction suggested by Figures 3.11 and 3.12 generate
equivalent generalized transition graphs.
15. Write a regular expression for the set of all C real numbers.
16. In some applications, such as programs that check spelling, we may not
need an exact match of the pattern, only an approximate one. Once the
notion of an approximate match has been made precise, automata theory can
be applied to construct approximate pattern matchers. As an illustration of
this, consider patterns derived from the original ones by insertion of one
symbol.
Let L be a regular language on Σ and define
insert (L) = {uav : a ∈ Σ,uv ∈ L}.
In effect, insert (L) contains all the words created from L by inserting a
spurious symbol anywhere in a word.
* (a) Given an nfa for L, show how one can construct an nfa for insert (L).
** (b) Discuss how you might use this to write a pattern-recognition program
for insert (L), using as input a regular expression for L.
12. Show how all the labels in Figure 3.14 were obtained.
13. Find a regular expression for the following languages on {a, b}.
(a) L = {w : n a (w) and n b (w) are both even}.
(b) L = {w :(n a (w) - n b (w)) mod 3 = 1}.
(c) L = {w :(n a (w) - n b (w)) mod 3 = 0}.
(d) L = {w :2n a (w)+3n b (w)is even}.
14. Prove that the construction suggested by Figures 3.11 and 3.12 generate
equivalent generalized transition graphs.
15. Write a regular expression for the set of all C real numbers.
16. In some applications, such as programs that check spelling, we may not
need an exact match of the pattern, only an approximate one. Once the
notion of an approximate match has been made precise, automata theory can
be applied to construct approximate pattern matchers. As an illustration of
this, consider patterns derived from the original ones by insertion of one
symbol.
Let L be a regular language on Σ and define
insert (L) = {uav : a ∈ Σ,uv ∈ L}.
In effect, insert (L) contains all the words created from L by inserting a
spurious symbol anywhere in a word.
* (a) Given an nfa for L, show how one can construct an nfa for insert (L).
** (b) Discuss how you might use this to write a pattern-recognition program
for insert (L), using as input a regular expression for L.