lOMoAR cPSD| 49343224
Downloaded by Vincent master ()
, lOMoAR cPSD| 49343224
Question 1 [15 marks]
A recursive definition for the language ODDnotAB over
the alphabet ∑ = {a b} must be compiled where
ODDnotAB has as elements all words that are of odd
length and do not contain the ab-substring.
Give (i) an appropriate universal set,
(ii) the generator(s) of ODDnotAB, and
(iii) an appropriate function on the universal
set, and then
(iv) use these concepts to write down a
recursive definition of the language ODDnotAB.
Answer
(i) The set {a b}* will be suitable because it contains,
along with other words, all the words that are in the
language ODDnotAB.
(ii) The generators are a and b. Note that the
generator(s) is/are always the shortest word(s) in a
language.
(iii) The function CONCAT as defined in learning unit
3, will be suitable. You can see how this function
has been used in Activity 3.1 in learning unit 3.
(iv) We give two possible recursive definitions. Note
the words in ODDnotAB have an odd number of
letters. Both generators have an odd number of
letters; therefore, to keep the length of new
generated words odd, we concatenate two letters at
a time. We also need to ensure that when we
concatenate strings to form new words that we do
Downloaded by Vincent master ()
, lOMoAR cPSD| 49343224
not add a word that starts with a b to a word that
ends with an a – this would result in words that
contain an ab-substring, and these words are not in
ODDnotAB. We will also not attempt to
concatenate the ab-substring to any existing words
in ODDnotAB as these words would also not be in
ODDnotAB.
ODDnotAB is the smallest
subset of {a b}* such that a,
b ODDnotAB
and if w ODDnotAB, then also
CONCAT(bb, w), CONCAT(w, aa)
ODDNOTAB, and
if w ODDNOTAB and w does not
end on a, then CONCAT(w, ba),
CONCAT(w, bb) ODDNOTAB,
if w ODDNOTAB and w does not begin with b, then
CONCAT(aa, w), CONCAT(ba, w) ODDNOTAB.
(this mark only once)
OR
Rule 1: a, b ODDNOTAB.
Rule 2: If w ODDNOTAB then
CONCAT(bb,w), CONCAT(w,aa)
ODDNOTAB, and if w
ODDNOTAB and w does not end on a,
then CONCAT(w,ba), CONCAT(w,
bb) ODDNOTAB, if w
ODDNOTAB and w does not begin with
b, then CONCAT(aa,w),
CONCAT(ba,w) ODDNOTAB.
Downloaded by Vincent master ()
, lOMoAR cPSD| 49343224
Rule 3: Only words generated by rules 1 and 2 are in
ODDNOTAB.
Question [15 marks]
2
This question has three parts and tests mathematical
induction.
(i) Give a recursive definition of the set P of all
positive integers greater than 0,
(ii) formulate the appropriate induction principle, and
then
(iii) use mathematical induction to prove that
11 + 15 + 19 + … + (4n + 7) = 2n2 + 9n
for all positive integers n > 0.
Answer
(i)P is the smallest subset of ę such that 1 P and if k
P then also k+1 P.
Another correct recursive definition for P is:
Rule 1: 1 P
Rule 2: If k P, then also k+1 P
Rule 3: Only elements generated by the above rules are in
P.
(ii) The applicable induction principle is:
If a subset A of P is such that 1 A and if k A
then also k+1 A, then A = P.
Downloaded by Vincent master ()
Downloaded by Vincent master ()
, lOMoAR cPSD| 49343224
Question 1 [15 marks]
A recursive definition for the language ODDnotAB over
the alphabet ∑ = {a b} must be compiled where
ODDnotAB has as elements all words that are of odd
length and do not contain the ab-substring.
Give (i) an appropriate universal set,
(ii) the generator(s) of ODDnotAB, and
(iii) an appropriate function on the universal
set, and then
(iv) use these concepts to write down a
recursive definition of the language ODDnotAB.
Answer
(i) The set {a b}* will be suitable because it contains,
along with other words, all the words that are in the
language ODDnotAB.
(ii) The generators are a and b. Note that the
generator(s) is/are always the shortest word(s) in a
language.
(iii) The function CONCAT as defined in learning unit
3, will be suitable. You can see how this function
has been used in Activity 3.1 in learning unit 3.
(iv) We give two possible recursive definitions. Note
the words in ODDnotAB have an odd number of
letters. Both generators have an odd number of
letters; therefore, to keep the length of new
generated words odd, we concatenate two letters at
a time. We also need to ensure that when we
concatenate strings to form new words that we do
Downloaded by Vincent master ()
, lOMoAR cPSD| 49343224
not add a word that starts with a b to a word that
ends with an a – this would result in words that
contain an ab-substring, and these words are not in
ODDnotAB. We will also not attempt to
concatenate the ab-substring to any existing words
in ODDnotAB as these words would also not be in
ODDnotAB.
ODDnotAB is the smallest
subset of {a b}* such that a,
b ODDnotAB
and if w ODDnotAB, then also
CONCAT(bb, w), CONCAT(w, aa)
ODDNOTAB, and
if w ODDNOTAB and w does not
end on a, then CONCAT(w, ba),
CONCAT(w, bb) ODDNOTAB,
if w ODDNOTAB and w does not begin with b, then
CONCAT(aa, w), CONCAT(ba, w) ODDNOTAB.
(this mark only once)
OR
Rule 1: a, b ODDNOTAB.
Rule 2: If w ODDNOTAB then
CONCAT(bb,w), CONCAT(w,aa)
ODDNOTAB, and if w
ODDNOTAB and w does not end on a,
then CONCAT(w,ba), CONCAT(w,
bb) ODDNOTAB, if w
ODDNOTAB and w does not begin with
b, then CONCAT(aa,w),
CONCAT(ba,w) ODDNOTAB.
Downloaded by Vincent master ()
, lOMoAR cPSD| 49343224
Rule 3: Only words generated by rules 1 and 2 are in
ODDNOTAB.
Question [15 marks]
2
This question has three parts and tests mathematical
induction.
(i) Give a recursive definition of the set P of all
positive integers greater than 0,
(ii) formulate the appropriate induction principle, and
then
(iii) use mathematical induction to prove that
11 + 15 + 19 + … + (4n + 7) = 2n2 + 9n
for all positive integers n > 0.
Answer
(i)P is the smallest subset of ę such that 1 P and if k
P then also k+1 P.
Another correct recursive definition for P is:
Rule 1: 1 P
Rule 2: If k P, then also k+1 P
Rule 3: Only elements generated by the above rules are in
P.
(ii) The applicable induction principle is:
If a subset A of P is such that 1 A and if k A
then also k+1 A, then A = P.
Downloaded by Vincent master ()
