Section 9.3 Finite-State Machines
757
45. Does the given string belong to the given regular set?
a. 01110111; (1*01)*(11 ~ 0*)
b. 11100111; 3(1*0)* ~ 0*114*
c. 011100101; 01*10*(11*0)*
46. Does the given string belong to the given regular set?
a. 1000011; (10* ~ 11)*(0*1)*
b. 011110; 0*11(1* ~ 10)
c. 101110; 3(101)*10*4*
47. Write a regular expression for the set of all arithmetic expressions indicating the addition or subtraction of
two positive integers.
48. Write a regular expression for the set of all alphanumeric strings beginning with a letter, which is the set
of legal identifiers in some programming languages.
49. Write regular expressions for each of the strings described in Exercise 25.
50. Write regular expressions for each of the strings described in Exercise 26.
51. Write regular expressions for each of the strings described in Exercise 27.
52. Write regular expressions for each of the strings described in Exercise 28.
53. a. Prove that if A is a regular set, then the set A
R
consisting of the reverse of all strings in A is also regular.
b. For any string a, let a
R
be the reverse string. Do you think the set 5aa
R
0 a [ I *6 is regular?
54. Prove that if A is a regular set whose symbols come from the alphabet I, then I * − A is a regular set.
A number of programming languages define “regular expressions” somewhat differently than we have done
in this chapter. In these instances, the regular expression is meant to describe a pattern for a set of strings so
that an arbitrary string can be matched against the pattern to see whether the string belongs in the set. Examples
are (a) searching a string to see whether it matches the format of a valid e-mail address and (b) extracting all
instances of the form href = “…” from an HTML document. Perl (Practical Extraction and Report Language)
is a language strong in text processing; following are some of the syntax rules for regular expressions in Perl.
*
repeat the preceding character or group 0 or more times [this is familiar]
?
repeat the preceding character or group 0 or 1 times
+ repeat the preceding character or group 1 or more times
.
(period)—matches any single character
.*
(period asterisk)—matches arbitrary string of any length
\s
(backslash lowercase s)—matches any whitespace character (space, tab, newline)
\S (backslash uppercase s)—matches any nonwhitespace character
For Exercises 55–62, decide which of the given strings match the given regular expression.
55. Regular expression: bet?er
Strings: beer, beter, better, bettter
56. Regular expression: bet*er
Strings: beer, beter, better, bettter
57. Regular expression: bet+er
Strings: beer, beter, better, bettter
58. Regular expression: b.?t
Strings: bit, but, beet, bt
59. Regular expression: b.+t
Strings: bit, but, beet, bt
60. Regular expression: b\St
Strings: bit, but, beet, b t
61. Regular expression: b\ st
Strings: bit, but, beet, b t
62. Regular expression: b\ s*t
Strings: bit, bt, b t, b t
757
45. Does the given string belong to the given regular set?
a. 01110111; (1*01)*(11 ~ 0*)
b. 11100111; 3(1*0)* ~ 0*114*
c. 011100101; 01*10*(11*0)*
46. Does the given string belong to the given regular set?
a. 1000011; (10* ~ 11)*(0*1)*
b. 011110; 0*11(1* ~ 10)
c. 101110; 3(101)*10*4*
47. Write a regular expression for the set of all arithmetic expressions indicating the addition or subtraction of
two positive integers.
48. Write a regular expression for the set of all alphanumeric strings beginning with a letter, which is the set
of legal identifiers in some programming languages.
49. Write regular expressions for each of the strings described in Exercise 25.
50. Write regular expressions for each of the strings described in Exercise 26.
51. Write regular expressions for each of the strings described in Exercise 27.
52. Write regular expressions for each of the strings described in Exercise 28.
53. a. Prove that if A is a regular set, then the set A
R
consisting of the reverse of all strings in A is also regular.
b. For any string a, let a
R
be the reverse string. Do you think the set 5aa
R
0 a [ I *6 is regular?
54. Prove that if A is a regular set whose symbols come from the alphabet I, then I * − A is a regular set.
A number of programming languages define “regular expressions” somewhat differently than we have done
in this chapter. In these instances, the regular expression is meant to describe a pattern for a set of strings so
that an arbitrary string can be matched against the pattern to see whether the string belongs in the set. Examples
are (a) searching a string to see whether it matches the format of a valid e-mail address and (b) extracting all
instances of the form href = “…” from an HTML document. Perl (Practical Extraction and Report Language)
is a language strong in text processing; following are some of the syntax rules for regular expressions in Perl.
*
repeat the preceding character or group 0 or more times [this is familiar]
?
repeat the preceding character or group 0 or 1 times
+ repeat the preceding character or group 1 or more times
.
(period)—matches any single character
.*
(period asterisk)—matches arbitrary string of any length
\s
(backslash lowercase s)—matches any whitespace character (space, tab, newline)
\S (backslash uppercase s)—matches any nonwhitespace character
For Exercises 55–62, decide which of the given strings match the given regular expression.
55. Regular expression: bet?er
Strings: beer, beter, better, bettter
56. Regular expression: bet*er
Strings: beer, beter, better, bettter
57. Regular expression: bet+er
Strings: beer, beter, better, bettter
58. Regular expression: b.?t
Strings: bit, but, beet, bt
59. Regular expression: b.+t
Strings: bit, but, beet, bt
60. Regular expression: b\St
Strings: bit, but, beet, b t
61. Regular expression: b\ st
Strings: bit, but, beet, b t
62. Regular expression: b\ s*t
Strings: bit, bt, b t, b t