Catching a spy and Infinity

I apologize for the hiatus, but I have been buried under overwhelming quantities of work lately. I'll take a break from the regular expression program to show you a puzzle I've found quite interesting:

(You can find more such puzzles here.)

Catching a spy

A spy is located on a one-dimensional line. At time 0, the spy is at location A. With each time interval, the spy moves B units to the right (if B is negative, the spy is moving left). A and B are fixed integers, but they are unknown to you. You are to catch the spy. The means by which you can attempt to do that is: at each time interval (starting at time 0), you can choose a location on the line and ask whether or not the spy is currently at that location. That is, you will ask a question like "Is the spy currently at location 27?" and you will get a yes/no answer. Devise an algorithm that will eventually find the spy.

 

Whoa, that looks quite difficult. Not only do you not know where A is (and there's a lot of places where it could be) but you don't know the spy's velocity either (or direction!). Do not fret, let's make baby steps.

First step: Since the numbers of unknowns and cases is quite large, let's answer a simple version of the question. Set A at 0 and let B only be positive. This means that we know that the thief starts from A = 0 and he's only moving towards the right. What now? Well, let's systematically try and eliminate values of B. Assume B = 1. Then, to rule this option out just ask at t = 1 “Is the spy at position 1?”. If he's not, that means that B ≠ 1. Ok, what about B = 2? At t = 2 ask “Is the spy at position 4?” as this is where he would be if B = 2. If he's not, that means that B ≠ 2. Keep going this way and at moment t ask “Is the spy at position B*t?”. Since we are systematically working our way up through the possible values of B, we know that after B questions we will find the thief!

Second step: Let's look at a more general case. Let B be negative as well. We have more possibilities to worry about (actually, it's just as many as before. Infinity is weird like that.). We can't try and be done with the positive values first and then start working on the negative ones, as we will never get there. Instead, we need to creep our way both directions at the same time. Alternate the positive and negative values of B that we are eliminating with each question. That is eliminate: 1, -1, 2, -2, 3, -3 etc. (Can you work out what positions you have to inquire about at each t?)

Third step: Great, now that we know how to check for all B, we can start worrying about the values of A which, until now, has been fixed. Oh dear, it looks like too many things are moving at the same time! Let's take a look at this (simple) table. Each row lists a value of A and each column a value of B. What we have to do now is find a way to traverse this table by making sure we hit each cell after only a finite amount of time. 

 

Note: We can work out a formula which tells us about which position to enquire at a given time. So, at moment t, if we want to eliminate value a for A and value b for B we can ask about position s(t,a,b) = a + t*b, since that is where the spy would be at that time.

How should we walk around the table? Trying to check the first row first would not work as we will never start checking the second row. Trying to go for the first column would not work either, for the same reason. Fear not, for there is a solution, given by Cantor. Simply take the following path. I'll let you figure out why each cell will be reached after a finite amount of time.

Here's some generalizations you might want to think about. It would help if you have some notions of infinity before thinking about some of these:

1. What if the spy runs around in 2 dimensions? That is, he is either moving up, down, left or right.
2. What about 3 dimensions? 4? Countably infinite ones?
3. What if A = 0 and B can take real values?
4. What if A = 0 and B can take positive real values, but at any given time t you can ask “Is the spy in the vicinity of x?” where x is a real number and by “vicinity” you mean in the interval (x-d, x+d) for a given, fixed d.
5. Same as above, but B can also be negative.
6. Same as above again, but now both A and B can take real values?

Turning NFAs into DFAs (the actual code)

See previous post.


Right, so now, given the bfs function we can convert a given NFA into a DFA. First off, think of the types. We use integers to represent the states of the NFA. The set of states for the DFA, however is the powerset of the set of states of the NFA. Then:

toDFA :: NFA Integer ab → DFA [Integer] ab

If the NFA is M(Q,S,d,q₀,F) then the equivalent DFA will be M'(Q',S,d',q₀',F') . Let's take them one by one. To obtain Q' we need a powerset function:

powerSet :: [a] → [[a]]

powerSet [] = [[]]

powerSet (x:xs) = ps ++ map (x:) ps

where ps = powerSet xs

The alphabet stays the same.

The initial state is the set of all the states that can be reached by epsilon transitions from q0. We need to write a function that will return this set. This is where we need to use the bfs we designed earlier:

--needs trans function, initial state

newInitialState :: Eq st => (Maybe ab -> st -> [st]) -> st -> [st]

newInitialState f q = bfs q (f Nothing)

By passing f Nothing as an argument to bfs we are only allowing epsilon transitions.

To compute F' we need:

That is:

--needs set of states OF THE DFA, final states OF THE NFA

newFinalStates :: Eq(st) => [[st]] -> [st] -> [[st]]

newFinalStates dfaqs nfafqs = [q | q <- dfaqs, not $ null $ intersect q nfafqs]

Next up, let's compute d'. This is going to be slightly more difficult to do. According to the definition of d', given a state and a symbol we need to return the list of all the states that can be reached by any number of epsilon transitions and only one s transition. Let's define a function that, given a node and a function returns that exact list. We'll call it neighbourStates:

neighbourStates :: Eq(st) => st -> ab -> (Maybe ab -> st -> [st]) -> [st]

neighbourStates q0 s f = ana (f Nothing) (nub$concat$map (f (Just s)) (nub((nub$concat$map (f Nothing) (dfs q0 (f Nothing))) ++ f (Just s) q0)))

Wow, that's a big definition. Here's the idea:

1. get a list of all the nodes reachable by only epsilon transitions
2. perform ONE s transition from each of the states in the list
3. for each state in the new list, find all the reachable nodes by epsilon transitions.

Turning into code:

1. Perform bfs by using only epsilon transitions. The problem with bfs, however, is that it includes the original node, regardless of whether there exists a path to it, or not. To avoid this problem, simply do another epsilon transition from all of the nodes in the list. That is:
   
   
   nub((nub$concat$map (f Nothing) (dfs q0 (f Nothing))) ++ f (Just s) q0))
   
   
2. Now, perform one s transition from all the odes in the list. Remember however, that we need to take care of q0, namely we need to take into account the s transitions that start straight from q0. Then:
   
   
   (nub$concat$map (f (Just s)) (nub((nub$concat$map (f Nothing) (dfs q0 (f Nothing))) ++ f (Just s) q0)))
   
   
3. From the new list, just do bfs using epsilon transitions from all the states in the list. We could just map bfs on the list, then do concat and nub, but we already have a function that does this for us: bfsaux
   
   
   bfsaux (f Nothing) (nub$concat$map (f (Just s)) (nub((nub$concat$map (f Nothing) (dfs q0 (f Nothing))) ++ f (Just s) q0)))

So that's the neighbourStates function. Then, we can build the actual transformation function! Here it is:

toDFA :: NFA Integer ab -> DFA [Integer] ab

toDFA (NFA voc sA fA s0A finA) = DFA voc sB fB (newInitialState fA s0A) (newFinalStates sB finA)

where sB = powerSet s

fB sym state = nub (concat [neighbourStates q sym fA | q <- state]);

Breath First Search in Haskell

Programming languages are, more or less, created equal. Despite different syntax and concepts, all decent languages are Turing complete. This means that they are part of the same class. There is no program that one can write in one language that one cannot write in another.

We know that we can perform Breath First Searches (BFS) in linear time in imperative languages. Intuitively, then, we should be able to write a linear time BFS in Haskell as well. Turns out we can, but it's too much of an effort. We'll settle for the next best thing.

Now, we are writing this bfs function for our Complementing Regular Expressions program, so we will choose a slightly odd way of representing the data. BFS works on a graph and a starting node and returns a list of all the reachable nodes from the start node. Instead of defining something like:

data Graph a = Node a [Graph a]

We will keep track of all the edges in the graph through a function f. Then, if q is a node then f q returns a list of all the reachable nodes from q.

f :: a → [a]

bfs :: a → (a → [a]) → [a]

The rather inelegant way we shall go about this is the following: At each step, we will maintain a list of all the nodes that we have visited so far called xs. At every iteration, for each visited node (so for every node in xs) we will try and add all its neighbours to xs. The iteration stops when no new nodes can be added. This is precisely what the bfsaux function does:

bfsaux :: Eq(a) => (a -> [a]) -> [a] -> [a]

bfsaux f xs = if next == [] then xs

               else bfsaux f (next ++ xs)

 where next = nub [y | x <- xs, y <- f x, (not . elem y) xs]

Note: nub ys is simply a function that deletes repeats in the list ys. Also, Eq(a) is required for elem y xs to work.

This is not efficient! One of the problems here is that, for most nodes in xs, we try adding their neighbours to xs at every iteration and we fail each time. All the checking and calling of f costs us time. One way to improve it is to split the information we carry from recursive call to recursive call into a pair (xs,ys) such that at every step we only try and add the neighbours of ys to xs and then we merge ys and xs. That is (xs , ys) → (nub(xs++ys) , next). However, our current implementation is sufficient for now. We can come back and change it if we wish so.

Then bfs is defined as:

bfs q f = bfsaux f [q]

Turning NFAs into DFAs

See previous post. | See next post

The first bit we are going to write is concerned with converting the NFA into a DFA. I am not going to prove that the two are actually equivalent, I'll only show the construction of the DFA. The idea here is that any NFA can be simulated by a DFA with an exponentially increased number of states. Think about it, when the NFA starts consuming the word it's been fed at each step it maintains active a number of sets. Upon consuming each letter, the set of active states changes according to the transition function:

If A is the set of active states at one point then, after one step the set of active positions will be:

We can simulate this by constructing a DFA which represents every possible combination of active NFA states. Then the number of states will be at least 2ⁿ, as any subset of the set of states in the NFA has to be represented.

The DFA transition rule will be the transition from A to A' shown above.

Let's express this formally so we'll be able to convert it to Haskell easily. If the NFA is M(Q,S,d,q₀,F) then the equivalent DFA will be M'(Q',S,d',q₀',F'):

• Q' is the set of all subsets of Q. That is the power set of Q
• S stays the same
• d' tells us where we can go from a state given a symbol. Then:
  

  

  Where q -> p means there exists a transition from q to p that involves only the symbol s and possibly some epsilon transitions.
  Note that this acts on sets of states from the NFA. This will prove to be a slight hindrance later on.
• q₀' will represent the starting position of the NFA. When M starts processing the word, the only active state is the initial state q₀. Then q₀' = {q₀}
• F' requires a bit of thought. When do we consider a word accepted by the NFA? When there is a path we can take through M such that we end up in an accepting state. However, our DFA keeps track of all the active states. Then, to consider a state as an accepting one in the DFA it must only accept words that are accepted in the NFA a well. So they must contain an accepting state of the NFA. Then:
  
  

  

Converting this to Haskell code will be fairly easy, baring some concerns about types. Before we get started on that, let us take a look at a DFS search on a graph in Haskell.

Setting up the frame

See previous post.  |  See next post.

First off, some definitions:

A DFA is formally defined as a 5-tuple (Q, S, d, q₀, F) where:

• Q is the set of all the states of the DFA
• S is the alphabet over which the DFA works
• d is the transition function. This is a very important part of the DFA as most of the information is encoded here. The result of the function d(s,q) is the state into which you move if you are in the state q and consume s.
• q₀ is the initial state
• F is the set of final states.

Similarly, a NFA is defined as (Q, S, d, q₀, F). All of the definitions are maintained as they were in the DFA. Two amendments are made, both of them to the transition function d:

• d can now accept e. This just represents an epsilon transition, which moves you to a state but does not consume a letter from the word you are reading.
• d will return a (possibly empty) set of states into which you move given a state and a symbol. The behaviour is different than that of a DFA as now you can have more than one active state at a given moment.

Since we'll be working in Haskell, let's think about the types of each element of the 5-tuple. Let the alphabet be of type ab and the states be represented by elements of type st. Then:

• Q is simply a set of states. We'll implement this as [st]
• S is the state of accepted symbols, that is type [ab]
• d needs a bit of care. It is a function which receives a symbol and a state and returns a state. That is: d :: ab → st → st.
• q₀ is a state, so just st
• F is a set of final states, so we'll implement it as [st]

Then the definition of a DFA over an alphabet [ab] that represents states as st is:

-- vocabulary, set of states, transition function, initial state, final states

data DFA st ab = DFA [ab] [st] (ab -> st -> st) st [st]

Note that DFA is both the name of the data type and the name of the constructor. This is clearer:

data DFA st ab = DFAconstructor [ab] [st] (ab -> st -> st) st [st]

However, I will be using the first definition.

Now to model the NFA: Things will pretty much stay the same, apart from the function which will require a bit of care. First of all, the function will return a set of states instead of a single state so:

d :: ab → st → [st]

gets us closer to our definition. The other amendment is that d also accepts e as a symbol. The best way to model this is to use the Maybe data type:

data Maybe a = Nothing | Just a

Then Just a will represent the symbol a and Nothing will represent the e symbol. Then:

-- vocabulary, set of states, transition function, initial state, final states

data NFA st ab = NFA [ab] [st] (Maybe ab -> st -> [st]) st [st]

About complementing regular expressions (in Haskell)

See next post. 


I've been trying to code in Haskell a small program that, given a regular expression and an alphabet, would return the complement regular expression (with respect to the given alphabet).

First, let's set up the idea for the program. Simply working with the regular expression itself and trying to manipulate it directly would make the logic of the function be very cumbersome. So how should we go about it?

We're going to use the relation between DFAs, NFAs and regular expressions, namely:

• any regular expression can be represented as an NFA
• any NFA has an equivalent DFA
• any DFA can be complemented (very easily)
• any DFA can be represented through a regular expression.

Our battle plan will thus be:

• parse the regular expression
• convert it to a NFA
• convert the NFA to a DFA
• complement the DFA
• convert the DFA into a regular expression

This allows us to split up the program into manageable chunks which we will deal with separately. You can see the solutions for these in the few next posts.

Hello World!

Hello World!

Well, this is awkward.