{0,1} * be defined by the
set of all strings a such thatBasic Definitions
Definition 1.1. An alphabet, A, is a finite set of distinct elements or characters: A={a1, a2, ...,an} .
Definition 1.2. A string, a, defined over an alphabet A is an ordered sequence of elements of A.
Definition 1.3. For a string a, |a| is defined as the length of a, that is, the number of characters in a.
Definition 1.4. For an alphabet A, A* is defined as the set of all strings over A.
Definition 1.5. A language, L, over an alphabet A is some subset of A*.
Definition 1.6. Let the language Q {0,1} * be defined by the
set of all strings a such that
if |a| = 1, then a=0
if |a| = 2, then a=00
if |a| = 3, then a=000
if |a| = 4, then a=000b for some b in {0,1} *.
Definition 1.7. For a in Q, define pF(a) as follows:
if a=0, then pF(a)=1
if a=00, then pF(a)=2
if a=000, then pF(a)=3
if |a|>3, then a=babc for some b in Q and some a,b,c elements of {0,1} , and
if c=0, then a=bab0 and pF(a)=pF(bab)+pF(b)
if c=1, then a=bab1 and pF(a)=pF(bab)+pF(ba).