The Computer Laboratory

Practice Paper 3 Question 14

The Seesat language has the single-letter word \(A.\) Longer words are built by applying a sequence of the following rules: Rule \(r_1\) says that if \(x\) is a word then \(Ax\) is a word; Rule \(r_2\) says that if \(x\) and \(y\) are words then \(Bxy\) is a word. For example, the sequence \(r_1(r_2(A,A))\) yields the word \(ABAA.\)

  1. Give a valid sequence of rules that yields the word \(AAABBAAA.\)
  2. Write \(N_A (x)\) and \(N_B(x)\) for the number of \(A\) and \(B\) letters in the word \(x\) respectively. By expressing \(N_A(x)\) and \(N_B(x)\) in connection with the rules, prove mathematically that \(N_A(x) > N_B(x)\) for any word \(x\) in the language.

The above links are provided as is. They are not affiliated with the Climb Foundation unless otherwise specified.

Warm-up Questions

  1. Prove, by mathematical induction, that \(\sum_{k=1}^{n}k^2 = \frac{n(n+1)(2n+1)}{6}.\)

Hints

  • Hint 1
    In simple terms, what do rule \(r_1\) and \(r_2\) do?
  • Hint 2
    How many times should you apply rule \(r_2\) to get \(AAABBAAA?\)
  • Hint 3
    If \(x\) is a word in the language, express \(N_A(r_1(x))\) in terms of \(N_A(x).\)
  • Hint 4
    Similarly, find \(N_B(r_1(x)),\) \(N_A(r_2(x,y))\) and \(N_B(r_2(x,y)),\) with \(y\) being another word in the language.
  • Hint 5
    What assumption do you need to make in order to claim that \(N_A(r_1(x)) > N_B(r_1(x))\) and \(N_A(r_2(x,y)) > N_B(r_2(x,y))?\)
  • Hint 6
    Is your assumption valid? Hint: Consider \(N_A(A)\) and \(N_B(A).\)
  • Hint 7
    Try proving by induction.
  • Hint 8
    ... more specifically, induction over each of the rules.

Solution

Starting with a single-letter word \(A,\) the rules allow us to create new words from existing ones. Rule \(r_1\) lets us add an \(A\) in front of a word, while rule \(r_2\) combines two words and adds a \(B\) in front. There are \(2\) \(B\)s in \(AAABBAAA,\) thus we must apply rule \(r_2\) twice: first to have \(BAA,\) then \(BBAAA.\) Hence, the sequence of rule is \(r_1(r_1(r_1(r_2(r_2(A,A),A)))).\)

In order to prove that \(N_A(x) > N_B(x)\) for any word \(x\) in the language, we use induction over each of the rules. The base case is simple, \(N_A(A) = 1 > 0 = N_B(A).\) For the inductive step, our assumption is that \(N_A(x) > N_B(x)\) and \(N_A(y) > N_B(y),\) for some words \(x\) and \(y\) in the language. We have to show that \(N_A(r_1(x)) > N_B(r_1(x))\) and \(N_A(r_2(x,y)) > N_B(r_2(x,y)):\)

  • \(r_1:\) \(N_A(r_1(x)) = 1 + N_A(x) > N_B(x) = N_B(r_1(x))\)

  • \(r_2:\) \(N_A(r_2(x,y)) = N_A(x) + N_A(y) > 1 + N_B(x) + N_B(y) = N_B(r_2(x,y)).\)

Hence, \(N_A(x) > N_B(x)\) for all words \(x\) in the language.

If you have queries or suggestions about the content on this page or the CSAT Practice Platform then you can write to us at oi.footasc@sulp.ecitcarp. Please do not write to this address regarding general admissions or course queries.