Deterministic Nonfinite Automaton - Longest Block of Ones

Question

How to Think About Algorithms - Jeff Edmonds

Exercise 2.2.2

The problem asks to find $\sum$, Q, δ, s, and F of this program if we see it as an automaton. Edmonds characterized this as deterministic non-finite automaton since 'n' is not bounded.

$\sum$ is {0,1} but I'm not sure how to model Q and the transition functions.

One guess is just simply Q = { q[p_max, q_max, length_max, p_current, length_current] }, with each of the 5 variables taking a value in the set of size around n ( { 1, 2, 3, ... , n} ), which will have O(n^5) states

but even if I use this brute force approach I can't easily define transition functions that determine the next state based on current state and the input read each iteration (0 or 1).

The biggest difficulty is modeling conditionals. When you are at a state q_1, the next state seems to be defined not just by 0 or 1 input but also by the length variables.

He didn't provide any solutions and I did a lot of research but still lost.

Any suggestions?

Answer 1

Your guess is definitely on the right track, though you may need one more piece of information. As you have infinite states (of which each input will use some number of them according to a function of the length of the input), you can use (as you observe) the states to encode information that deals with the length of the input.

There are a number of ways to do this (you can use the same variables as the code essentially), but I think it's clearer to be more explicit. Each state can keep track of the following six things:

1. The starting position of the best run so far.
2. The ending position of the best run so far.
3. The length of the best run so far.
4. The starting position of the current run being counted.
5. The ending position of the current run being counted.
6. The length of the current run being counted.

So each state could be labeled something like:

$$q_{maxstart,maxend,maxlength,currentstart,currentend,currentlength}$$

This then solves the transition problem:

• A zero in the input ends the current run, and resets to start counting again, but doesn't affect the best run so far
• A one in the input increases the end point of the current run (and sets the starting point if the current run length is zero) AND if you happen to be in a state where the current run length is the same as the best run length, it also alters the best run length subscripts (that is, the transition takes you to a state where those change suitably).

There's no branching in either of those, so the process is completely deterministic.

A couple of examples to illustrate:

• The start state is easy, it's just $q_{0,0,0,0,0,0}$ with the transitions $\delta(q_{0,0,0,0,0,0},0) = q_{0,0,0,1,1,0}$ and $\delta(q_{0,0,0,0,0,0},1) = q_{0,1,1,0,1,1}$. This uses the case where the current run length is the same as the best, and we see a one, so we update the best start and end to be the same as the current start and end etc.
• Now let's try a state where the current run changes, but isn't better than the best. Imagine we're in state $q_{a,b,50,x,y,3}$, then the two transitions will be $\delta(q_{a,b,50,x,y,3},0) = q_{a,b,50,y+1,y+1,0}$ and $\delta(q_{a,b,50,x,y,3},1) = q_{a,b,50,x,y+1,4}$.

This actually pretty much covers all the cases (as there's really not much going on except the abuse of subscripts to count for us).

To boil that down to some rules for putting in the transitions:

1. $\delta(q_{a,b,n,x,y,m},0) = q_{a,b,n,y+1,y+1,0}$
2. If $m < n$, $\delta(q_{a,b,n,x,y,m},1) = q_{a,b,n,x,y+1,m+1}$
3. If $m = n$, $\delta(q_{a,b,n,x,y,n},1) = q_{x,y+1,n+1,x,y+1,n+1}$

You don't need any states where $m > n$, so you don't have to worry about that case (though you can include them and give them a rule like #3 if you want a complete infinite enumeration of all the subscripts.

Answer 2

Based on Luke Mathieson's amazing answer,

and using the concept of an "empty"** block from the book

i.e. A[i..j] is empty is i > J;

The transition functions can be modeled as follows (difference being how we update starting position of the current run using the empty block):

δ( Q[p, q, leng_max, p_c, i, leng_curr] , 0 ) = Q[p, q, leng_max, i+2, i+1, 0]

the other two transition functions are excellently described in Luke's answer