Section 1.3

1. (a) $0,5,10,15,20$ is one such list.

(c) MATH is one such list.

(g) $1,2,4,6,10$ is one such list.

2. (c) MATH

(d) $1,3$

3. (a) MATH is one such list.

(b) MATH is one such list.

(c) MATH is one such list.

The sets in parts (a) and (b) contain the empty word $\lambda $; the set in part (c) does not since MATH

8. (c) $\ 138$

10. (a) $2$

(b) $\infty $

(c) $\infty $

(d) $3$

(e) $8$

(f) MATH

13. (a) $aba$ belongs to MATH and $\sum_{3}^{\ast }$. In each case its length is $3$.

(b) $bAb$ belongs to $\sum_{3}^{\ast }$ only. Its length is $2$.

(c) $cba$ belongs to $\sum_{1}^{\ast }$ only. Its length is $3$.

(d) $cab$ belongs to $\sum_{1}^{\ast }$ and $\sum_{2}^{\ast }$. Its length in $\sum_{1}^{\ast }$ is $3,$ while its length in $\sum_{2}^{\ast }$ is $2.$

(e) $caab$ belongs to $\sum_{1}^{\ast }$ and $\sum_{2}^{\ast }$. Its length in $\sum_{1}^{\ast }$ is $4,$ while its length in $\sum_{2}^{\ast }$ is $3.$

(f) $baAb$ belongs to $\sum_{3}^{\ast }$ only. Its length is $3.$

14. You would never arrive at the word $ba$ in this dictionary assuming that you had to go

through all the words prior to it first. That's because there are infinitely many words prior

to it, e.g. $a,aa,aaa,aaaa,$ etc ...

To figure out how far you would have to dig to get $ba$ in case the dictionary contained only words

of length 5 or less ... Let's count the words appearing before $ba$. These must start with the letter $a$, or be

just the single letter $b$ itself. How many words start with $a?$ There is one of length 1 (just $a$), 2 of length 2

$(aa$ and $ab$), 4 of length 3 ($aaa,aab,aba,abb)$, 8 of length 4 (you can list them if you want) and 16 of

length 5. Thus the number of words appearing before $ba$ in this special dictionary is 1+2+4+8+16+1 = 32.

So $ba$ is the 33rd word in this dictionary.

This document created by Scientific Notebook 4.1.