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.
-
- Prove, by mathematical induction, that
$\sum_{k=1}^{n}k^2 = \frac{n(n+1)(2n+1)}{6}.$
- Prove, by mathematical induction, that
-
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. -