594 APPENDIX B Finite Automata
- The standard way to describe the individual tokens ("words") of a computer language
is with regular expressions orfinite state automata. We gave examples in Appendix A;
here, we just consider a simple example. The regular expression (a lbb)* means that
a string may be built up by any number of occurrences of a's or bb's-for example,
abbaaabb consists of one a, followed by one bb, followed by three a's, followed
by one bb. The symbol I means exclusive or; the symbol * (called the Kleene star)
means any number of occurrences-including 0. The language denoted by the regular
expression is the set of all strings that can be built that way:{A,a,aa,bb,aaa,abb,bba,aaaa,aabb,abba,bbaa,bbbb ....
where the symbol A just names the empty string-the string consisting of 0 symbols.
(a) Previously, we listed all strings of length less than or equal to four in the language
denoted by (a Ibb)*. Assume there are four strings of length four in the language.
Find, and solve a recurrence relation for the number of strings of length n in the
language for arbitrary non-negative integer n.
(b) Find and solve a recurrence relation for the number of strings of length n in the
language denoted by (a I bbIc)*.
(c) Find and solve a recurrence relation for the number of strings of length n in the
language denoted by (a I bbIcc)*.
(d) How many strings of length n are there in the language denoted by
(albblc)*J(albblcc)*? Why?