# 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.\)

- Give a valid sequence of rules that yields the word \(AAABBAAA.\)
- 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.

## Related topics

## Warm-up Questions

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

## Hints

- Hint 1In simple terms, what do rule \(r_1\) and \(r_2\) do?
- Hint 2How many times should you apply rule \(r_2\) to get \(AAABBAAA?\)
- Hint 3If \(x\) is a word in the language, express \(N_A(r_1(x))\) in terms of \(N_A(x).\)
- Hint 4Similarly, 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 5What 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 6Is your assumption valid?
*Hint:*Consider \(N_A(A)\) and \(N_B(A).\) - Hint 7Try 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.. Please do not write to this address regarding general admissions or course queries. tasc@sulp.ecitcarp