Lets examine FSAs whose transition functions are FULL BINARY TREES. We can call these objects FBTSAs to help you remember that they are full binary trees. The alphabet of an FBTSA is = {0, 1}, the start state is at the root, transition arrows must go away from the root and toward the leaves, and all transitions out of the leaves are to a fail state (not drawn). Like a normal FSA, any state can be either accepting or rejecting, except the fail state, which always rejects.

a. Give the language and an English description for the FBTSA on the right:

b. Draw an FBTSA and give an English description of the language {00, 01, 10, 11}.

c. Using big-O notation, give an upper bound for the word length in the language of any FBTSA in terms of the number of states |S|. Please explain your answer.

d. Using big-O notation, give an upper bound for the number of accepted words in the language of any FBTSA in terms of the number of states |S|. Please explain your answer.

e. Using big-O notation, give an upper bound for the number of possible languages of an FBTSA in terms of the number of states |S|. Please explain your answer.

O O O O OO OO