Section 3.1 Recursive Definitions
177
49. A set S of strings of characters is defined recursively by
1. a and b belong to S.
2. If x belongs to S, so does xb.
Which of the following strings belong to S?
a. a
b. ab
c. aba
d. aaab
e. bbbbb
50. A set W of strings of symbols is defined recursively by
1. a, b, and c belong to W.
2. If x belongs to W, so does a(x)c.
Which of the following strings belong to W ?
a. a(b)c
b. a(a(b)c)c
c. a(abc)c
d. a(a(a(a)c)c)c
e. a(aacc)c
51. A set S of integers is defined recursively by
1. 0 and 3 belong to S.
2. If x and y belong to S, so does x + y.
Use structural induction to prove that every integer in S is a multiple of 3.
52. A set T of strings is defined recursively by
1. pqq belongs to T.
2. If x and y belong to T, so do pxqq, qqxp, and xy.
Use structural induction to prove that every string in T has twice as many q’s as p’s.
53. Give a recursive definition for the set of all unary predicate wffs in x.
54. Give a recursive definition for the set of all well-formed formulas of integer arithmetic, involving integers
together with the arithmetic operations of +, −, * , and /.
55. Give a recursive definition for the set of all odd integers.
56. Give a recursive definition for the set of all strings of well-balanced parentheses.
57. Give a recursive definition for the set of all binary strings containing an odd number of 0s.
58. Give a recursive definition for the set of all binary strings containing an even number of 1s.
59. Give a recursive definition for the set of all binary strings ending with 0.
60. Give a recursive definition for the set of all binary strings with an equal number of 0s and 1s.
61. Use BNF notation to define the set of positive integers.
62. Use BNF notation to define the set of decimal numbers, which consist of an optional sign (+ or −),
followed by one or more digits, followed by a decimal point, followed by zero or more digits.
63. Give a recursive definition for x
R
, the reverse of the string x.
64. Give a recursive definition for 0 x 0 , the length of the string x.
65. Give a recursive definition for the factorial operation n! for n ≥ 1.
177
49. A set S of strings of characters is defined recursively by
1. a and b belong to S.
2. If x belongs to S, so does xb.
Which of the following strings belong to S?
a. a
b. ab
c. aba
d. aaab
e. bbbbb
50. A set W of strings of symbols is defined recursively by
1. a, b, and c belong to W.
2. If x belongs to W, so does a(x)c.
Which of the following strings belong to W ?
a. a(b)c
b. a(a(b)c)c
c. a(abc)c
d. a(a(a(a)c)c)c
e. a(aacc)c
51. A set S of integers is defined recursively by
1. 0 and 3 belong to S.
2. If x and y belong to S, so does x + y.
Use structural induction to prove that every integer in S is a multiple of 3.
52. A set T of strings is defined recursively by
1. pqq belongs to T.
2. If x and y belong to T, so do pxqq, qqxp, and xy.
Use structural induction to prove that every string in T has twice as many q’s as p’s.
53. Give a recursive definition for the set of all unary predicate wffs in x.
54. Give a recursive definition for the set of all well-formed formulas of integer arithmetic, involving integers
together with the arithmetic operations of +, −, * , and /.
55. Give a recursive definition for the set of all odd integers.
56. Give a recursive definition for the set of all strings of well-balanced parentheses.
57. Give a recursive definition for the set of all binary strings containing an odd number of 0s.
58. Give a recursive definition for the set of all binary strings containing an even number of 1s.
59. Give a recursive definition for the set of all binary strings ending with 0.
60. Give a recursive definition for the set of all binary strings with an equal number of 0s and 1s.
61. Use BNF notation to define the set of positive integers.
62. Use BNF notation to define the set of decimal numbers, which consist of an optional sign (+ or −),
followed by one or more digits, followed by a decimal point, followed by zero or more digits.
63. Give a recursive definition for x
R
, the reverse of the string x.
64. Give a recursive definition for 0 x 0 , the length of the string x.
65. Give a recursive definition for the factorial operation n! for n ≥ 1.