0
$\begingroup$

How to Think About Algorithms - Jeff Edmonds

Exercise 2.2.2

Here is the code from the book

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?

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ so 'd(q<maxstart,maxend,maxleng,currstart,currend,currlength>,1) = (next_state)'. If I were to write a few transition functions for this automaton to cover all cases, how can I differentiate the above case where the longest block changes and when it doesn't? I totally understand your points but I was aiming for a set of transition functions that govern all cases for this automaton. something like 'd(q<a,b,x,i,j,y>, 0) = q<a,b,x,i+2,j,y> if we follow the given algorithm exactly. $\endgroup$ – namesake22 Dec 13 '17 at 16:26
  • $\begingroup$ and that is why I was curious as to how to incorporate the conditional in such transition functions $\endgroup$ – namesake22 Dec 13 '17 at 16:29
  • $\begingroup$ @namesake22 I made the rules more explicit. $\endgroup$ – Luke Mathieson Dec 13 '17 at 23:07
  • $\begingroup$ Okay, I just didn't think we could add if-conditionals to transition functions like you did in rule 2 and 3. I was only trying to make the functions fit the form of rule 1, which must have been a stubborn idea. $\endgroup$ – namesake22 Dec 14 '17 at 5:18
  • 1
    $\begingroup$ @namesake22 They're not really conditionals on the transitions, you just make all the states, and depending on what the label of the state is, you either at a #2 or a #3, you don't choose during the computation. $\endgroup$ – Luke Mathieson Dec 14 '17 at 5:42
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.