Issued: Friday, March 5
Due: Tuesday, March 30, 2pm

• Graphs
• Implementing Graphs
  • Problem 1: Exits, Existence of Edges and Path Verification
• Finite Automata
  • Problem 2: The Automaton Class
  • Problem 3: Traversal
  • Problem 4: Simulation
  • Problem 5: path?
  • Problem 6: Inaccessible States
  • Problem 7: The Product Construction

WARNING!!
This problem set is even more difficult than the last one. This is not a sit-down-in-one-night-and-crank-it-out problem set; in fact, this isn't a sit-down-in-three-nights-and-crank-it-out problem set. You should start on it early, at the very least to get ideas about the questions floating around in your head. Do NOT let this problem set go until the last minute!

Note that all of the problems in the problem set are such that a little bit of thought will save you tremendous headaches. You should attempt to write out solutions to each question well before you sit down at the computer.

Note also: sample output provided is a sample only. You need to demonstrate that your functions work correctly on a sufficiently wide range of inputs. One of your tasks in this problem set is to decide what needs to be tested and to do so. Show us the output of these tests.

Last word of advice: filter and map are very, very useful functions, and can be used to make your life so incredibly much easier. Take advantage of that fact.

Graphs

In this problem set, we will be investigating graphs and automata. What is a graph? Well, a graph consists of two things: a set of points (called vertices (or sometimes nodes)) and a set of lines connecting those points (called edges). Formally, a graph is an ordered pair G = (V,E) where V = the set of vertices and E = the set of edges.

Edges are themselves represented by an ordered pair of vertices. Edges can have direction (in which case the graph is called directed) or not (in which case the graph is called undirected). In a directed graph, the edge (u, v) is the edge from u to v. Note that (v,u), the edge from v to u, is different from (u,v), whereas in an undirected graph, the edge (v, u) is the same as the edge (u, v).

This is an example of a directed graph. The vertices are A, B, C, and D, or in set notation, V = {A, B, C, D}. The edges are represented by (mathematical, not Scheme) pairs; the first element of the pair is where the edge comes from. The second is where is edge goes. So E = {(A, B), (B, C), (B, D), (D, C)}.

We refer to a path between two vertices u and v as an ordered sequence of edges [(u, u₁), (u₁, u₂), ..., (u_n, v)]. For example, in the graph shown, there is a path from A to C, namely [(A, B), (B, C)]. The path [(A, B), (B, D), (D, C)] is also a path from A to C, although it is longer. Often, a path will be abbreviated to the sequence of vertices traveled in that path. So, the path from A to D would be abbreviated into the sequence [A, B, D].

Implementing Graphs

There are two standard ways of representing a graph in memory: an adjacency matrix or an adjacency list. An adjacency matrix keeps a two-dimensional array indexed by the vertices of the graph in both directions. Cell (i,j) contains 1 if and only if there is an edge from vertex i to vertex j in the graph. An adjacency list, on the other hand, maintains for each vertex a list of vertices adjacent to it. For example, the graph   would be represented as

	U	V 	W
       ===     ===     ===
U	0	0	1
V	1	1	0
W	0	1	0

in an adjacency matrix, and as

U: (W)  
V: (U V)
W: (V)

in an adjacency list. There are advantages to each representation: for example, attempting to discover whether an edge exists between two vertices (u and v) is simply a matter of accessing a single cell Adj[u,v] in an array with an adjacency matrix, an O(1) operation. In an adjacency list, however, one must look through the entire list of vertices adjacent to u and see if v appears. There can be as many as V vertices in the list of vertices adjacent to v, so it could take as much as O(V) time to find whether v is adjacent to u. The advantage of using adjacency lists is that if we ever need to do anything to all the edges, we can simply cdr down the lists for each vertex and do whatever we need to do. This runs in O(E) time, while with an adjacency matrix, we need to look at every cell of the array (since we don't know whether there is an edge between two vertices until we check that cell), which is O(V²) time. An easy way to see this is to look at the size of the representation: with an adjacency matrix, there are V² entries in the array, regardless of the number of edges, while an adjacency list has one element in a list per edge in the graph.

We will implement graphs using something like adjacency lists because the graphs we are dealing with are going to be (generally) sparse graphs, which means that E<<V^2 ("E is much less than V^2"). (Intuitively, the sparcity of a graph directly corresponds to the density of "0"s in an adjacency matrix representation of the graph.) In sparse graphs, the advantages of the adjacency list outweigh its disadvantages greatly. So that's what we'll use.

We have provided three predefined classes in the code, <graph>, <vertex>, and <edge>. The graph type has two slots, both lists: one a list of <vertex>s, the other a list of <edge>s. The vertices contain only names, but the directed-edges contain two vertices, as discussed above.

Two important graph functions have been defined for you. The function find-vertex takes a name of a vertex and a list of vertices, and finds the vertex in the list with the name given. The function returns #f if no such vertex exists, and the actual <vertex> if it does.

The function create-graph is a little more complicated. This function takes in a list of symbols (which will become the names of vertices) and a list of lists which describe the edges of the graph. The structure of the edge list is as follows:

((U1 U2) (U3 U4) ... )

where the Us are the names of vertices contained in the vertex list. (Although this relation is not actually checked by the function, it easily could have been.) In the actual call to make-graph inside create-graph, map is used in a fairly clever way. You should look over this code, because you will be writing similar functions throughout the problem set.

Problem 1: Exits, Existence of Edges and Path Verification

Using the given graph functions and type definitions, write a function exits which, given a graph and a vertex in the graph, returns a list of vertices that can be reached from the vertex by following a single edge in the graph. (This function will be very useful for later problems.)

Also implement a predicate is-edge? which, given a graph and two vertices in the graph, returns #t just in case there is an edge from the first vertex to the second in the given graph. (Note that this function is trivial once you've completed the first part of this exercise.)

Define a path in a graph as follows: a path from vertex u to vertex v in graph G is a (non-empty) list of vertices in G connected by edges, starting with u and ending with v. Write a function verify-path, which takes a graph and a list of vertices, and verifies that the list is indeed a valid path (from the first element in the list to the last element in the list) in the given graph. Give an informal argument that your function has a running time which is polynomial in its input. (Let m be the number of edges in the graph, let n be the number of nodes number of vertices in the graph, and let p be the number of elements in the alleged path. verify-path runs in polynomial time if, for some constants a,b,c, verify-path runs in time O(m^a n^b p^c).)

Sample Output:

==> (define g1 (create-graph '(a b c d e)
                             '((a b) (a c) (b c) (b e) (c d) (d b))))
==> (display-vertices (exits (find-vertex 'b (get-graph-vertices g1)) g1))
(c e)
==> (is-edge? (find-vertex 'a (get-graph-vertices g1))
              (find-vertex 'b (get-graph-vertices g1)) g1)
#t
==> (is-edge? (find-vertex 'c (get-graph-vertices g1))
              (find-vertex 'a (get-graph-vertices g1)) g1)
#f
==> (verify-path (map (lambda (x) (find-vertex x (get-graph-vertices g1)))
                      '(a b c d b e))
                 g1)
#t
==> (verify-path (map (lambda (x) (find-vertex x (get-graph-vertices g1))) '()) g1)
#f
==> (verify-path (map (lambda (x) (find-vertex x (get-graph-vertices g1)))
                 '(a d b)) g1)
#f

For this problem, turn in your definitions of exits, is-edge? and verify-path, and output showing the functions working, as well as an informal running-time analysis of verify-path.

Finite Automata

A DFA (deterministic finite automaton (plural: automata)) is a directed graph in which the edges are labeled, i.e. each edge has a name associated with it. The set of possible symbols that can be in labels is called the alphabet of the automaton. In a finite automaton, vertices are called states. The function of an automaton is to scan an input sequence one symbol at a time, and decide whether to "accept" the sequence or not. These theoretical machines are useful in pattern matching and compilers. They are also used all the time (in slightly modified form) in hardware.

You can think of a DFA as a kind of map (a road map, that is, not the function map). The states of the automaton are towns, and the edges are one-way roads going between them. One state is the starting point, called the start state. Any number of states (including possibly the start state) are designated as final states. The "goal" is to traverse (travel along) the roads, starting at the start state and ending at one of the final states.

To do this, you are given a sequence, which we will represent by an ordered list of characters. Think of these as tokens in a Pez dispenser (or elements on a stack, if you're too young to remember Pez). You need the tokens to pay a toll on the road, and different toll booths require different tokens. It's like a Pez dispenser (or stack) because you can only use the first token you have (the top of the stack), and you can't take it out of the dispenser (off the stack) unless you use it (pop the stack). Moreover, for DFA's each token must be used in order.

So use the input symbols one at a time, removing the first one whenever a transition labeled with that character is traversed (you pay the toll). If at any time there is no transition that can be traversed, you "lose" the game (since you're stuck and can't move anywhere). If this does not happen, when you run out of characters, you "win" if you are in a final state. Sequences of characters which make you "win" represent "accepted" sequences, and those that make you "lose" are "rejected". The usefulness of DFA's comes from the types of sequences that they accept.

The D in DFA stands for deterministic. This means that whenever you move in the automaton, you have no choices. You are either forced along one route by the character at the front of the remaining sequence, or you're stuck and the sequence is rejected. (That is, there is at most one transition with a given symbol from each state.)

Formally, a DFA is a collection of 5 things:

For clarity, in the examples given below we will always denote states by letters and use the fixed alphabet {0, 1}. In the code you write, however, you need to assume that these can be arbitrary.

A nondeterministic finite automaton (NFA) is just like a DFA except for one minor detail. In an NFA, there can be many transitions that apply at any given time. Going along with the Pez dispenser analogy, this means that whenever you stand at an intersection, there could be many roads that require your current Pez as their toll. A traversal through the machine requires you to choose which transition to take when there is more than one possibility. (In particular, this also means that there can be more than one start state --- you have to pick where to start, too.)

For an NFA, making bad choices doesn't hurt you. In other words, if there exists any "good" choice of traversal, then the machine accepts the input, regardless of how many bad choices there are.

In this problem set, we will not worry ourselves with anything other than automata in general (which will be like NFAs under this description, since a DFA is a special case of an NFA).

Problem 2: The Automaton class

Define a new class <labeled-edge> as a subclass of <edge>. Give the class a new slot, label. Write a function display-labeled-edges, analagous to display-edges.

Now define a new class <automaton> as a subclass of <graph>. Give this class the slots for a list of start states (of <vertex>s) and final states (of type <list> of vertices). (NFAs have multiple start states, so we need to have the capacity to have multiple start states in our automata. That's why we need a list of start states for <automaton>s in general.)

Also define a constructor create-automaton analogous to create-graph.

==> (define dfa1 
    (create-automaton '(a b c)
                      '((a a 0) (a b 1) (b a 1) (b c 0) (c b 0) (c c 1))
                      '(a)
                      '(a)))

This dfa (as you will see) accepts binary numbers divisible by 3. You should draw this out on a piece of paper to convince yourself.

For this problem, turn in your type and constructor definitions for the types <labeled-edge> and <automaton>.

Problem 3: Traversal

Now that we've defined most of the underlying structure for the automata, one thing is still missing: the notion of the delta function, which takes a state and an input symbol and returns a list of destination states. The encoding for this relation is in the labeled edges of the graph.

Define a function step taking an <automaton>, a current state name, and and input symbol. Given a state, step returns a list of the names of all possible states reachable from that state.

Sample Output:

==> (step dfa1 'c 1)
(c)
==> (step dfa1 'd 0)
()
==> (step dfa1 'a 2)
()
==> (define nfa2
      (create-automaton '(a b c)
			'((a a 0) (a b 0) (a b 1) (b a 1) 
			  (b c 0) (c b 0) (c c 1))
			'(a)
			'(a)))
==> (step nfa2 'a 0)
(a b)

For this problem, turn in your definition of step and output showing your function working.

Problem 4: Simulation

Now, with step as our tool, we can simulate the operation of an automaton on an entire input list. Define a function simulate which takes in an automaton and an input "string" (a list of characters, actually) and returns #t if the machine accepts the string and #f otherwise. The simulate function should track all the states that the machine could be in after scanning each character of the input, and then check to see whether it could possibly be in a final state. If the machine could reach a final state by some choice of moves, then the machine accepts its input.

Test your function on both a DFA and on the NFA in the diagram. The red states are the final states and the start state is A. Transitions labeled "0, 1" are just shorthand for two transitions which have the same endpoints, but different labels. This NFA accepts sequences which either begin or end with 1 (or both). This automaton is nondeterministic, since from state C, given a 1, you can stay in C or go to D. The advantage of this is that if you encounter a 1 in state C, you "choose" to go to state D only if it's the last symbol in the sequence.

Sample Output (uses DFA dfa1, defined in Problem 2):

==> (simulate dfa1 '(1 0 0 1))
#t
==> (simulate dfa1 '(1 0 1 1))
#f
==> (define (divis-by-3? n)
        (simulate dfa1 (decimal->binary-list n)))
==> (divis-by-3? 12)
#t
==> (divis-by-3? 19)
#f

For this problem, submit your definition for simulate, along with examples of your code working.

Problem 5: path?

(Warning: this is probably the hardest question that you will be asked to solve all semester. Do not sit down and start hacking -- THINK!)

Write a function path? which, given a generic graph (we're leaving behind the world of automata) and two vertices, determines whether there is some path between the two vertices. The function returns #t if some path exists and #f if there is no such path.

Think about this problem well before you start typing. You must write a paragraph description of your algorithm in addition to coding it!

Recommendations: Draw some graphs on a piece of paper, and think about how you would determine the answer for any graph. Use ideas that you have developed over the previous problems. These aren't automata anymore, but you know more about graphs than you may think. How is a general graph like an NFA?

In computer science, this is generally known as a decision algorithm, since you are determining a property of the graph, but you're not actually finding the path (but think about how you would do it).

Sample Output:

? (path? g1 (find-vertex 'a (get-graph-vertices g1))
            (find-vertex 'e (get-graph-vertices g1)))
==> #t

For this problem, turn in your definition of path?, a paragraph description of how your algorithm works (you should write this *before* you start coding!), and demonstration that it works properly.

Problem 6: Inaccessible states

Let's go back in the land of automata .... In some machines, there are some states which are completely inaccessible from the start state. That is, no matter *what* the input to the machine, it will never land in these states. It's easy to see these in a picture: these are just the state that have no arrows connecting them from the start state. But the internal representation of automata may not make it so easy to discover which states are inaccessible. Now that you've written path?, however, it shouldn't be so hard.

Write a function remove-inaccessible-states that takes an <automaton> and returns another <automaton> that has no inaccessible states. Be sure to remove the transitions to and from inaccessible states, as well.

==> (define dfa1-reduced (remove-inaccessible-states dfa1))
==> (display-vertices (get-automaton-vertices dfa1-reduced))
(a b c)
==> (display-vertices (get-automaton-vertices dfa1))
(a b c)
==> (display-labeled-edges (get-automaton-edges dfa1))
((a 0 a) (a 1 b) (b 1 a) (b 0 c) (c 0 b) (c 1 c))
==> (display-labeled-edges (get-automaton-edges dfa1-reduced))
((a 0 a) (a 1 b) (b 1 a) (b 0 c) (c 0 b) (c 1 c))

==> (define dfa3 (create-automaton '(a b c d)
                                 '((a b 0) (a b 1) (c d 0) (c d 1))
                                 '(a)
                                 '(b c)))
==> (define dfa4 (remove-inaccessible-states dfa3))
==> (display-vertices (get-automaton-vertices dfa3))
(a b c d)
==> (display-vertices (get-automaton-vertices dfa4))
(a b)
==> (display-labeled-edges (get-automaton-edges dfa3))
((a 0 b) (a 1 b) (c 0 d) (c 1 d))
==> (display-labeled-edges (get-automaton-edges dfa4))
((a 0 b) (a 1 b))
==> (display-vertices (get-automaton-final-states dfa3))
(b c)
==> (display-vertices (get-automaton-final-states dfa4))
(b)

For this problem, turn in your definition of remove-inaccessible-states, and output showing it working properly.

Problem 7: The Product Construction

Suppose that we have defined an automaton to accept binary strings divisible by 3 and another to accept binary strings divisible by 5. You might suppose that an automaton that accepts binary strings divisible by 15 would be intimately related to these two automata. You'd be right. Here's the intuition: if we run the two automata for strings divisible by 3 and 5 on the input, and both automata accept the string, then that string is divisible by both 3 and 5, and therefore by 15.

The idea for doing this is quite simple: if x is to be accepted by both machine M and machine N, you could run M on x and N on x and accept just in case both accept. To turn this into a single machine, there's something called the product construction that takes two automata and creates a new automata accepting all strings accepted by both.

To do this, we create a new machine with the following elements (where M and N are the input machines):

• States are ordered pairs of states from M and N.
• The final states are ordered pairs of all final states of M and all final states of N.
• The start states are ordered pairs of all start states of M and all start states of N.
• The transitions from a state (p,q) is the set of all ordered pairs (u.v), where (p u) is an edge in M and (q v) is an edge in N.

Write a function product that takes two automata and creates a new automaton that accepts a string x just in case both of the automata accept x. For example:

==> (define dfa-divis-by-two
       (create-automaton '(d e) '((d d 0) (d e 1) (e e 1) (e d 0)) '(d) '(d)))
==> (define dfa-divis-by-six (product dfa-divis-by-two dfa1))
==> (display-vertices (get-automaton-start-states dfa-divis-by-six))
(d-a)
==> (display-vertices (get-automaton-vertices dfa-divis-by-six))
(e-a e-b e-c d-a d-b d-c)
==> (display-vertices (get-automaton-final-states dfa-divis-by-six))
(d-a)
==> (display-labeled-edges (get-automaton-edges dfa-divis-by-six))
((e-a 0 d-a) (e-b 0 d-c) (e-c 0 d-b) (e-a 1 e-b) (e-b 1 e-a) (e-c 1 e-c)
 (d-a 1 e-b) (d-b 1 e-a) (d-c 1 e-c) (d-a 0 d-a) (d-b 0 d-c) (d-c 0 d-b))

(Note: it is fine if your code produces these edges in different order.)

==> (simulate dfa-divis-by-six (decimal->binary-list 12))
#t
==> (simulate dfa-divis-by-six (decimal->binary-list 15))
#f
==> (simulate dfa-divis-by-six (decimal->binary-list 4))
#f
==> (simulate dfa-divis-by-six (decimal->binary-list 5))
#f
==> (simulate dfa-divis-by-six (decimal->binary-list 42))
#t