Problem 1 (5.20 from text)
A finite automaton consists of a set of states, which we shall take to be the integers 1..n and a table transitions[state, input] giving a next state for each state and each input character. For our purposes, we shall assume that the input is always either 0 or 1. Further, certain of the states are designated accepting states. For our purposes, we shall assume that all and only the even numbered states are accepting. Two states p and q are equivalent if either they are the same state, or (i) they are both accepting or both nonaccepting, (ii) on input 0 they transfer to equivalent states, and (iii) on input 1 they transfer to equivalent states. Intuitively, equivalent states behave the same on all sequences of inputs; either both or neither lead to accepting states. Write a program using the MFSET operations that computes the sets of equivalent states of a given finite automaton.
Problem 2
Consider an undirected graph G = (V,E) with n = |V| and m = |E|. The degree of a vertex is the number of edges incident on that vertex. Let di be the degree of vertex vi, Show that:
SUM[1..n]( di ) = 2m
Problem 3
In a directed graph, we can talk about in-degree and out-degree, the number of edges, respectively, arriving and leaving a given vertex. Show that the sum of the in-degrees of a graph is equal to the sum of the out-degrees.
Problem 4 (6.1 from text)
Represent the digraph of Fig. 6.38:
By an adjacency matrix give arc costs
By a linked adjacency list with arc costs indicated
