COS2601 Theoretical Computer Science II Example examination paper and solutions

COS2601 Theoretical Computer Science II Example examination paper and solutions (a) Let S = {a bb bab abaab}. For each of the following strings, state whether or not it is a word in S*: (i) abbabaabab (ii) abaabbabbbaabb (2) (b) Give an example of a set S such that S* only contains all possible strings of combinations of a’s and b’s that have length divisible by three. (4) (c) Give an example of two sets S and T of strings such that S* = T* but S ⊄ T and T ⊄ S. (4) ANSWER TO QUESTION 1 (a)(i) No, because there are no concatenations of a, bb, bab and abaab that will yield the word abbabaabab. (a)(ii) Yes, concatenations of a, bb, bab and abaab will yield the word: (abaab)(bab)(bb)(aa)(bb). (b) There is only one possible set S: S = {aaa aab aba abb baa bab bba bbb}. All the words in S* are multiples of three as all the words of S are of length exactly 3. (c) We give two possible answers; there are many other possibilities: S = {Λ a} and T = {a aa} or S = {a b ab} and T = {a b ba}. QUESTION 2 [10] A recursive definition for the language ODDAB should be compiled. Consider the alphabet ∑ = {a, b} and the language ODDAB, where ODDAB consists of all words of odd length that contain the substring ab. Provide (i) an appropriate universal set, (1) (ii) the generator(s) of ODDAB, (2) (iii) an appropriate function on the universal set, and then (1) (iv) use these concepts to write down a recursive definition for the language ODDAB. (6) ANSWER TO QUESTION 2 (i) The set {a b}* will be suitable because it contains, along with other words, all the words that are in the language ODDAB. (ii) The generators should be the smallest words in ODDAB of odd length and should contain the substring ab. Thus, aba, aab, abb, bab will be suitable generators. (iii) The function CONCAT as defined in the study guide will be suitable. (iv) We give two possible recursive definitions. Note that all words in ODDAB should have an odd number of letters. The generators all have an odd number of letters; therefore, to keep the length of new words odd, we concatenate two letters at a time. Note, the generator(s) is/are always the smallest word(s) in a language. ODDAB is the smallest subset of {a, b}* such that COS2601 Theoretical Computer Science II aba, aab, abb, bab ∈ ODDAB, and if w ∈ ODDAB, then also CONCAT(w, aa), CONCAT(w, bb), CONCAT(w, ab), CONCAT(w, ba), CONCAT(aa, w), CONCAT(bb, w), CONCAT(ab, w), CONCAT(ba, w) ∈ ODDAB. Or an alternative definition: Rule 1: aba, aab, abb, bab ∈ ODDAB. Rule 2: If w ∈ ODDAB, then also CONCAT(w, aa), CONCAT(w, bb), CONCAT(w, ab), CONCAT(w, ba), CONCAT(aa, w), CONCAT(bb, w), CONCAT(ab, w), CONCAT(ba, w) ∈ ODDAB. Rule 3: Only words produced by rules 1 and 2 are in ODDAB. QUESTION 3 [10] (i) Give a recursive definition of the set P of all positive integers greater than or equal to 5, (1) (ii) formulate an appropriate induction principle, and (2) (iii) then apply the induction principle to prove that 2n – 3 ≤ 2n-2 for all integers n ≥ 5. (7) ANSWER TO QUESTION 3 (i) P is the smallest subset of Z (the set of integers) such that 5 ∈ P and if n ∈ P, then also n + 1 ∈ P. (ii) If a subset A of P is such that 5 ∈ A, and if n ∈ A, then also n + 1 ∈ A, then A = P. (iii) Define A ⊆ P as follows: A = {n ∈ P | 2n – 3 ≤ 2n-2 } Is 5 ∈ A? 2(5) - 3 ≤ 25 - 2 i.e. 7 ≤ 8 Thus, 5 ∈ A is true. Assume k ∈ A, i.e. we assume that 2k – 3 ≤ 2k – 2 Required to prove that k + 1 ∈ A, i.e. 2(k + 1) –3 ≤ 2(k + 1) – 2 . LHS = 2(k + 1) – 3 = 2k + 2 – 3 = (2k – 3) + 2 ≤ 2k – 2 + 2 (from induction assumption (1)) ≤ 2⋅2 k – 2 (because the smallest value for 2 k – 2 with k = 5 is 2 5 – 2 = 8 and 2⋅8 = 16 10 = 25 – 2 + 2) = 21 + k – 2 = 2 (k +1) – 2 = RHS Thus k + 1 ∈ A Hence, A = P so we conclude that 2n - 3 ≤ 2n - 2 for all integers n ≥ 5. COS2601 Theoretical Computer Science II QUESTION 4 [10] (a) Does the regular expression [b*+ (abb*)* + (aabb*)*]* bbb [b* + (abb*)* + (aabb*)*]* define the language of all words in which the substring bbb appears at least once, but the substring aaa does not appear at all? If not, give a counterexample. (5) (b) Give a regular expression generating the language consisting of all words containing exactly one occurrence of the substring aa and no occurrence of the substring bb. (5) ANSWER TO QUESTION 4 (a) It is indeed the case that all words generated by the given regular expression contain the substring bbb. It is furthermore the case that no word generated by the given regular expression contains the substring aaa. However, not all such words (i.e. words containing the substring bbb but not the substring aaa) can be generated by the given regular expression. Some examples are: babbb aabbb bbba. The answer to this question is thus no, and the words above serve as counterexamples. (b) The regular expression that we need to give must make provision for words that start (and end) with either an a or a b. All occurrences of the letter b (except if it is the last letter of the word) must be followed by an a. Furthermore, only one a may be followed by another a - in order to ensure only one occurrence of the substring aa. A possible regular expression is: (b + Λ)(ab)*aa(ba)*(b + Λ) This is of course not the only possibility. QUESTION 5 [10] Build an FA (finite automaton) that accepts the language of all words that satisfies both of the following conditions: • NO word contains the substring bba, and • ALL words end with a double letter, thus all words end with either aa or bb. Note: Only one FA must be built. CAI tutorial: Remember to use the CAI tutorial Automata available on CD or downloadable from the web. In preparation for this question, you can navigate through all the sections in the tutorial. Graphical illustrations are also provided. (Please refer to section 1 in this tutorial letter.) ANSWER TO QUESTION 5 We do not need to keep track of the number of letters that have been read at any stage - even or odd is irrelevant for this question. A dead-end state is necessary to make provision for all words containing the bba-substring. You should further keep in mind that words ending on aaa or bbb are, of course, also permissible. From the initial state 1, we move to state 2 with an a and to state 3 with a b. From state 2, we move to a final state 4 with an a and if we read an a in the final state, we stay in the final state, because words such as aaa and aaaa are permissible words in the language. From state 3, we move to a final state, state 5, with a b and if we read a b in the final state, we stay in the final state, because words such as bbb and bbbb are permissible words in the language. If, however, we read an a in state 5, we move to a deadend state, state 6, from which we cannot leave because then the word contains the impermissible substring bba. The incomplete FA is given below: COS2601 Theoretical Computer Science II If we read a b in state 2, we go to state 3 and if we read an a in state 3, we move to state 2. What happens if a b is read in state 4? We move to state 3. - 1 2 3 + 5 6 a a, b b a b b + 4 a a - 1 2 3 + 5 6 a a, b b a b b + 4 a a a b b COS2601 Theoretical Computer Science II QUESTION 6 [10] By using Kleene’s theorem, find a regular expression that generates the language accepted by the following TG (transition graph): - ba b + + a b a aa bb a ANSWER TO QUESTION 6 Step 1 - Create a unique start state (note: this is actually redundant for this question because there are no incoming edges to the start state) and a unique final state: COS2601 Theoretical Computer Science II Step 2 - Eliminate state 3: Step 3 - Eliminate state 4: Step 4 - Eliminate state 2: Step 5 – Eliminate state 1: A possible regular expression is: [a + (b + bab*aa)(bb)*a]a* + (b + bab*aa)(bb)* Note that one can follow a different order in applying Kleene’s theorem to the states of the FA, and the regular expression may look somewhat different.