Copyright © 2003 by K. Stromswold 1

Lab 8: Grammar 1: Finite State Automata

The goal of this lab is to write a finite state automaton that characterizes the messages that are generated by a commercially available toy phone.

1. Press the left "message" button on the phone and write down the message that you hear. Do this 50 times (i.e., write down 50 messages)

2. Press the right "message" button on the phone and write down the message that you hear. Do this 50 times (i.e., write down 50 messages).

3. Based on the 50 messages generated by hitting the left 'message' button and the right 'message' button, do you think that the messages produced by hitting the two buttons are generated by a one finite state automaton or two distinct finite state automata? (If you think that there are two finite state automata, answer questions 4-8 for both automata)

4. Divide the messages into chunks that correspond to states in a finite state automaton.

5. Identify all possible members of each of the linearly ordered states

6. Identify all possible transitions from one state set to the next state set.

7. Determine the number of distinct strings that the device can generate, using the information obtained in 4, 5, and 6. Show your calculations.

8. List at least 1 example that your finite state automaton should generate, but which were not encountered in the first 100 messages.

9. Extra credit 1: Discuss the notions of competence and performance, as it pertains to question 8.

10. Extra credit 2: How would you go about determining whether the transitional probabilities from each member of each state the same?