CS 390 Solutions to Unit 5 Exercises



pp. 75 - 80

2.59 (a)   We are going to prove (xy)r = yrxr by induction on string y for an arbitrary fixed x. To review the definition of the set of strings over an alphabet click here.

Basis Step: If y = , then (xy)r = (x)r = xr and yrxr = rxr = xr = xr.
Hence (xy)r = yrxr when y = .
Inductive Step: Assume that (xy)r = yrxr holds for an arbitrary string y. --- Induction Hypothesis
We are going to show that (x(ya))r = (ya)rxr holds for any symbol a in .
(x(ya))r = ((xy)a)r by the associativity of concatenation
= a(xy)r by the definition of reversal
= a(yrxr) by the induction hypothesis.
= (ayr)xr by the associativity of concatenation
= (ya)rxr by the definition of reversal

Thus (xy)r = yrxr for any strings x and y.

This can also be proven by induction on the length of y.

2.35   We are going to prove that | xr | = | x | for any string x by induction on x, where | x | denotes the length of string x. The recursive definition of length of string is given elsewhere.

Basis Step: If x = , then | xr | = | r | = | |.
Hence | xr | = | x |.
Inductive Step: Assume that | xr | = | x | for an arbitrary string x. --- Induction Hypothesis
We are going to show that | (xa)r | = | xa |.
By the definition of reversal (xa)r = axr.
By the definition of | x | ,   | axr | = | xr | + 1.
Hence | (xa)r | = | xr | + 1.
By the induction hypothesis | xr | = | x |.
Hence | axr | = | x | + 1.
Also | ax | = | x | + 1.
Hence | axr | = | ax |.

2.39 (a)   Since the strings of L are generated from a by appending a or b any number of times and in any order, L is the set of strings of a's and b's that start with a.



2.40 (c)   T is the set of positive integers that are multiples of 2 and/or 7. It is defined recursively as follows:
Basis Clause: 2 and 7 T.
Inductive Clause: If x T, then nx T for every positive integer n.
Extremal Clause: Usual one.

2.65   Firstly, if a string x is in L, then since it can be generated from by adding one a and one b at a time, x has the same number of a's and b's.
We prove the converse, that is, if a string w has the same number of a's and b's, then it is in L, by induction on the length of w using the second principle of mathematical induction.

Let w be an arbitrary string that has the same number of a's and b's.
Assume that all the strings which are shorter than w and which has the same number of a's and b's are in L. --- Induction Hypothesis
We are going to show that w is in L.

Without loss of generality assume that w starts with a. Then there is a string z such that w = az. Scan the string z from its left end until the first such b that the number of b's exceeds that of a's both in z exactly by one. Let us denote that b by b0.
Let z = xb0y. Then x has the same number of a's and b's and so does y. Note that x and/or y might be empty. Then w = axb0y. Since by the induction hypothesis x and y are in L. Since w is obtained from them as axb0y, it is also in L according to the definition of L.
Thus we have proven that if a string w has the same number of a's and b's, then it is in L.