A challenging task in such an application is to write an efficient program for
recognizing string patterns. Searching a file for occurrences of a given string is a
very simple programming exercise, but here the situation is more complicated.
We have to deal with an unlimited number of arbitrarily complicated patterns;
furthermore, the patterns are not fixed beforehand, but created at run time. The
pattern description is part of the input, so the recognition process must be
flexible. To solve this problem, ideas from automata theory are often used.
If the pattern is specified by a regular expression, the pattern-recognition
program can take this description and convert it into an equivalent nfa using the
construction in Theorem 3.1.Theorem 2.2 may then be used to reduce this to a
dfa. This dfa, in the form of a transition table, is effectively the pattern-matching
algorithm. All the programmer has to do is to provide a driver that gives the
general framework for using the we can automatically handle a large number of
patterns that are defined at run time.
The efficiency of the program must also be considered. The construction of
finite automata from regular expressions using Theorems 2.1 and 3.1 tends to
yield automata with many states. If memory space is a problem, the state
reduction method described in Section 2.4 is helpful.
EXERCISES
1.Use the construction in Theorem 3.1 to find an nfa that accepts the language L
(ab*aa + bba*ab).
2.Find an nfa that accepts the complement of the language in Exercise 1.
3. Give an nfa that accepts the language L((a + b)* b(a + bb)*).
4. Find dfa's that accept the following languages.
(a) L (aa* + aba*b*).
(b) L (ab (a + ab)* (a + aa)).
(c) L ((abab)* + (aaa* + b)*).
(d) L (((aa*)* b)*).
5. Find dfa's that accept the following languages.
(a) L = L (ab*a*)∪ L ((ab)* ba).
recognizing string patterns. Searching a file for occurrences of a given string is a
very simple programming exercise, but here the situation is more complicated.
We have to deal with an unlimited number of arbitrarily complicated patterns;
furthermore, the patterns are not fixed beforehand, but created at run time. The
pattern description is part of the input, so the recognition process must be
flexible. To solve this problem, ideas from automata theory are often used.
If the pattern is specified by a regular expression, the pattern-recognition
program can take this description and convert it into an equivalent nfa using the
construction in Theorem 3.1.Theorem 2.2 may then be used to reduce this to a
dfa. This dfa, in the form of a transition table, is effectively the pattern-matching
algorithm. All the programmer has to do is to provide a driver that gives the
general framework for using the we can automatically handle a large number of
patterns that are defined at run time.
The efficiency of the program must also be considered. The construction of
finite automata from regular expressions using Theorems 2.1 and 3.1 tends to
yield automata with many states. If memory space is a problem, the state
reduction method described in Section 2.4 is helpful.
EXERCISES
1.Use the construction in Theorem 3.1 to find an nfa that accepts the language L
(ab*aa + bba*ab).
2.Find an nfa that accepts the complement of the language in Exercise 1.
3. Give an nfa that accepts the language L((a + b)* b(a + bb)*).
4. Find dfa's that accept the following languages.
(a) L (aa* + aba*b*).
(b) L (ab (a + ab)* (a + aa)).
(c) L ((abab)* + (aaa* + b)*).
(d) L (((aa*)* b)*).
5. Find dfa's that accept the following languages.
(a) L = L (ab*a*)∪ L ((ab)* ba).