POW#4 Spring 2022

Solutions due by noon on Friday, March 4

This diagram [1] is called a finite automaton. You give it a sequence of bits (0s and 1s), and its job is to either accept or reject that sequence.

Here's how it works. Begin by pointing at the circle that has an arrow pointing at it from nowhere, and then follow arrows according to the bit sequence. When you run out of bits, check if the circle you're pointing at has a double ring. If so, the finite automaton accepts the sequence.

For example, suppose your sequence is 1001. You would begin in circle A. The first bit (1) would move you to B. The second bit (0) would move you to A. The third bit (0) would keep you in A. The fourth bit (1) would move you to B. Now you're out of bits, and B has a double ring, so you would accept this sequence. In fact, this finite automaton will accept all (and only) the bit sequences that end with a 1.

Can you describe all the bit sequences that would be accepted by the finite automaton in diagram [2]?

This problem is brought to you by Prof. Lisa Torrey.

Back to Problems of the Week