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.$

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

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

In simple terms, what do rule $r_1$ and $r_2$ do?

How many times should you apply rule $r_2$ to get $AAABBAAA?$

If $x$ is a word in the language, express $N_A(r_1(x))$ in terms of $N_A(x).$

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.

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))?$

Is your assumption valid? Hint: Consider $N_A(A)$ and $N_B(A).$

Try proving by induction.

… more specifically, induction over each of the rules.

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.