Finite automata questions

Topics

• finite automata
• regular languages
• Knuth-Morris-Pratt string-matching algorithm

Finite automata

Draw a finite-automaton state transition table that accepts bit-strings representing numbers divisible by 5.

Answer.

Describe the strings accepted by the following finite automaton with a start state of a and accepting state of e.

             _
  __        /1\        ______          _____
 / 0\    1  \ L  0    / 1    v   1    / 0,1 \
 \-->a ----> b ----> c       d ----> e <-----
     ^              /^______/
     \_____________/0      0

Answer.

Describe the strings accepted by the following finite automaton with a start state of a and accepting states a, b, and c.

         _________
        /    _    \0
  __   /    /1\    \  1______
 / 0\ L  1  \ L  0  \ /      v
 \-->a ----> b ----> c <---- d
             ^           0  /
             \_____________/1

Answer.

Find a finite automaton that accepts bit strings such that every sequence of four consecutive characters contains a 1.

Answer.

Find a finite automaton that accepts strings from the alphabet a, b, c, and d which contain at least one a, one b, and one c.

Answer.

Find a finite automaton that accepts bit strings whose last five bits include a 1.

Answer.

What is the finite state automaton for the GameChannel class of Assignment 5? The automaton has 6 states.

• A. CHANNEL_CLOSED
• B. AWAITING_I_AM_MESSAGE
• C. AWAITING_OPPONENT_MOVE
• D. OPPONENT_MOVE_RECEIVED
• E. AWAITING_MY_MOVE
• F. TIMEOUT_WARNING_RECEIVED

1. openConnection() called
2. gameStatus() called
3. receiveMove() called
4. sendMove() called
5. TIMEOUT received from server
6. opponent's move received from server
7. final game status received from server
8. I_AM_X received from server
9. I_AM_O received from server

Answer.

Regular languages

Which of the following are regular? Write regular expressions for those that are. (You can use a period `.' to represent any character in the alphabet (``(a_1|a_2|a_3|...|a_k)'', if the a_i are the characters in the alphabat).)

1. the set of all strings
2. strings containing both ``smile'' and ``frown'' as substrings
3. strings containing 211 as a subsequence (211 is a subsequence of ``25-100 is a 12-credit course'' because it contains 211 in order)
4. bit sequences representing numbers that are both prime and perfect. (A number n is perfect if the sum of its factors (except n) is n itself.)

Answer.

Write a regular expression for bit strings representing numbers divisible by 3.

Answer.

If I have regular languages L1 and L2, is the set of strings in L1 but not in L2 also regular? Prove your answer.

Answer.

Knuth-Morris-Pratt string-matching

What is the next array for aardvark? For tartans?

Answer.

Challenge problem: Sometimes the inner while loop of the Knuth-Morris-Pratt may execute Omega(log n) times. Show that this can occur. (A proof would take an arbitrary n0 and find some pattern of length n>n0 so that in processing some text string the inner loop will iterate at least c lg n0 times, for some constant c.)

Answer.