Description

Programming Assignment

This assignment deals with the implementation of some utilities for finite automata. It restricts only to DFA and NFA, and does not deal with ε-NFA. In short, you are asked to carry out the following tasks.
• Read the data for an NFA N = (QN,Σ,∆,S,FN) from a file.
• Use the subset-construction procedure to convert the input NFA to an equivalent DFA D = (Q,Σ,δ,s,F).
• Use a graph-traversal algorithm to find out all reachable (or accessible) states in D.
• Remove all unreachable states from D to get a DFA D′ = (Q′,Σ,δ′,s′,F′).
• Find all groups of equivalent states in D′.
• Collapse each group of equivalent states in D′ to a single state, and generate the resulting minimized DFA
D .
Part 1: Representing DFA and NFA
Figure 1: An NFA for E6 and its representation in a file
22
2
0 12 -1
11 14 16 18 20 21 -1
0 0 0
0 0 1
0 1 0
0 1 2
1 0 3
1 1 4
2 0 4
3 0 5
3 1 6
4 0 6
5 0 7
5 1 8
6 0 8
7 0 9
7 1 10
8 0 10
9 1 11
10 0 11
12 0 13
12 1 14
13 0 15
13 1 16
14 0 16
15 0 17
15 1 18
16 0 18
17 0 19
17 1 20
18 0 20
19 1 21
20 0 21
-1
Write a function readNFA(filename) to read the input file, and store the information in a user-defined data structure
N. Store n and m as integer fields in N. For an NFA, S, F, and all ∆(p,a) are subsets of QN. Assume that n = |QN| < 32, so we can store a subset of QN as a bit array in a 32-bit unsigned integer variable. For example, for the NFA of Figure 1, we have the binary storage of the following subsets. The bits are numbered 0,1,2,3,…,31 from the least significant end. The i-th bit is 1 if i is in the subset; it is 0 otherwise.
S = {0,12} = 0000 0000 0000 0000 0001 0000 0000 0001,
FN = {11,14,16,18,20,21} = 0000 0000 0011 0101 0100 1000 0000 0000,
∆(0,1) = {0,2} = 0000 0000 0000 0000 0000 0000 0000 0101,
∆(19,0) = 0/ = 0000 0000 0000 0000 0000 0000 0000 0000.
It follows that a single 32-bit unsigned integer variable suffices to store each of S and FN. A two-dimensional n×m matrix of 32-bit unsigned integer variables can, on the other hand, store the entire transition table ∆(p,a).
Write two functions printNFA(N) and printDFA(D) to print the information stored in an NFA or a DFA data type, in the format illustrated in the sample output. If D contains too many (like > 64) states, it is preferable to skip the printing of the final states and the transition table of D.
In this assignment, you are required to handle your own data structures for storing sets of states. Do not use any set data type available in any library (like the STL). Not only the bit-level storage specified above is spaceefficient but also using a general-purpose set library will likely lead to infeasible running times for Part 2 which deals with exponential numbers of states.
Part 2: NFA-to-DFA conversion by subset construction
Write a function subsetcons(N) that, given an NFA N as input, returns an equivalent DFA D obtained by the subsetconstruction procedure. Here, N and D must be in the format specified in Part 1. We have Q = 2QN, that is, the states of Q are subsets of the set of states of N. With the bit-level storage of sets, the states of D have a natural one-to-one correspondence with the sets of states of N (that is, members of 2QN). Let P ⊆ QN be a state of D. For each a ∈ Σ, we have δ(P,a) = [∆(p,a). Each ∆(p,a) for N is a set stored as a 32-bit unsigned integer. Therefore
p∈P
the set union in the above formula is nothing but the word-level OR of ∆(p,a) values. You nevertheless need to find the bits set in P, but that too can be carried out efficiently by bit-wise operators.
Bit-wise operators
The bit-wise OR of two 32-bit unsigned integers V and W can be computed as in the following examples.
U = (V | W); W |= V;
Let j ∈ {0,1,2,…,31} be a bit position. The j-th bit in W can be set as:
W |= (1U << j);
In order to check whether the j-th bit in W is set, check whether the following expression is non-zero.
(W & (1U << j))
Part 3: Finding and removing unreachable states in a DFA
Let D = (Q,Σ,δ,s,F) be a DFA (like the one obtained in Part 2). D can be considered as a directed graph (with possible self-loops). Run a graph-traversal algorithm (depth-first search seems to be the easiest) starting from the start state s. After the traversal completes, the visited array (a set of DFA states) stores the states that can be reached from s. The remaining states in Q are unreachable, and can be thrown away from Q with impunity.
Write a function findreachable(D) to return the set R of states of D reachable from s, and another function rmunreachable(D,R) to return an equivalent DFA D in which all the states not in R are removed. Let n = |Q|, and n′ = |Q′| (so n′ 6 n). By our convention, we represent Q = {0,1,2,…,n−1} and Q′ = {0,1,2,…,n′ − 1}. After some states are thrown out from Q, a renumbering of the remaining states is necessary for Q′. Moreover, the transition table for D should be revised to the transition table for D′ in order to reflect this renumbering.
Part 4: Finding and collapsing equivalent states in a DFA
The main function
• The user supplies the name of a file storing the information about the input NFA N. Call readNFA to read the file, and store the information in an NFA data type N. Print N.
• Call subsetcons on N to obtain the DFA D. Print D (skip printing very long lists).
• Call findreachable to obtain the list R of states reachable from s in D. Print the members of R.
• Call rmunreachable to get the DFA D′ from D. Print D′.
• Call findequiv to obtain the two-dimensional array M.
• Call collapse to generate the minimal DFA D′′. Print D′′.
Sample output
Let us consider the following families of languages over the binary alphabet {0,1}. For each of these families, k is a positive integer-valued parameter.
Lk The k-th last symbol of x is 1o,
Ak The last k symbols of x contains at least one 1o,
Ek The last k symbols of x contains exactly one 1o.
All strings in Lk are of length > k. On the other hand, Ak and Ek are allowed to contain strings x of length < k with the interpretation that x must contain at least one or exactly one 1. An NFA for E6 is already given in Figure 1. NFA for L6 and A6 are supplied in Figures 2 and 3. Also, consider the following language over {0,1,2,3}. Figure 4 shows an NFA for this language, directly converted from the (unoptimized) regular expression 3∗03∗13∗23∗ +3∗03∗23∗13∗ +3∗13∗03∗23∗ +3∗13∗23∗03∗ +3∗23∗03∗13∗ +3∗23∗13∗03∗. The sample output for E6 is given below. Outputs for L6, A6, and B can be obtained from the course web-site.
B x contains each of the symbols 0,1,2 exactly onceo.
Figure 2: An NFA for L6

Figure 4: An NFA for B

Figure 5: The minimal DFA for E6

The minimal DFA for E can be obtained from the first principles (see Figure 5). The output DFA D′′ from your
6
program should be isomorphic to this DFA. The state numbers obtained in the sample are shown beside the states in Figure 5. The logical names appear inside the circles.
+++ Input NFA
Number of states: 22
Input alphabet: {0,1}
Start states: {0,12}
Final states: {11,14,16,18,20,21}
Transition function
Delta(0,0) = {0,1}
Delta(0,1) = {0,2}
Delta(1,0) = {3}
Delta(1,1) = {4}
Delta(2,0) = {4} Delta(2,1) = {}
Delta(3,0) = {5}
Delta(3,1) = {6}
Delta(4,0) = {6} Delta(4,1) = {}
Delta(5,0) = {7}
Delta(5,1) = {8}
Delta(6,0) = {8} Delta(6,1) = {}
Delta(7,0) = {9}
Delta(7,1) = {10}
Delta(8,0) = {10}
Delta(8,1) = {}
Delta(9,0) = {}
Delta(9,1) = {11}
Delta(10,0) = {11}
Delta(10,1) = {}
Delta(11,0) = {}
Delta(11,1) = {}
Delta(12,0) = {13}
Delta(12,1) = {14}
Delta(13,0) = {15}
Delta(13,1) = {16}
Delta(14,0) = {16} Delta(14,1) = {}
Delta(15,0) = {17}
Delta(15,1) = {18}
Delta(16,0) = {18} Delta(16,1) = {}
Delta(17,0) = {19}
Delta(17,1) = {20}
Delta(18,0) = {20}
Delta(18,1) = {}
Delta(19,0) = {}
Delta(19,1) = {21}
Delta(20,0) = {21}
Delta(20,1) = {}
Delta(21,0) = {}
Delta(21,1) = {}
+++ Converted DFA
Number of states: 4194304
Input alphabet: {0,1}
Start state: 4097
4128768 final states
Transition function: Skipped
+++ Reachable states: {5,19,21,75,83,85,299,331,339,341,683,1195,1323,1355,1363,1365,2731,3243,3371,3403,3411,3413,4097,8195,16389,
32779,65555,65557,131115,262219,262227,262229,524459,1048875,1048907,1048915,1048917,2098347,2098475,2098507,
2098515,2098517}
+++ Reduced DFA after removing unreachable states
Number of states: 42
Input alphabet: {0,1}
Start state: 22
Final states: {16,17,18,19,20,21,24,26,27,29,30,31,33,34,35,36,37,38,39,40,41} Transition function
ap| 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41
—+——————————————————————————————————————————
0 | 1 3 4 6 7 8 11 12 13 14 10 16 17 18 19 20 10 16 17 18 19 20 23 25 26 28 29 30 32 33 34 35 10 37 38 39 40 16 17 18 19 20
1 | 0 2 0 5 2 0 9 5 2 0 21 15 9 5 2 0 21 15 9 5 2 0 24 27 0 31 2 0 36 5 2 0 41 9 5 2 0 15 9 5 2 0
+++ Equivalent states
Group 0: {0}
Group 1: {1}
Group 2: {2}
Group 3: {3}
Group 4: {4}
Group 5: {5}
Group 6: {6}
Group 7: {7}
Group 8: {8}
Group 9: {9}
Group 10: {10,22,23,25,28,32}
Group 11: {11}
Group 12: {12}
Group 13: {13}
Group 14: {14}
Group 15: {15}
Group 16: {16}
Group 17: {17,37}
Group 18: {18,33,38}
Group 19: {19,29,34,39}
Group 20: {20,26,30,35,40}
Group 21: {21,24,27,31,36,41}
+++ Reduced DFA after collapsing equivalent states
Number of states: 22
Input alphabet: {0,1}
Start state: 10
Final states: {16,17,18,19,20,21} Transition function
ap| 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
—+——————————————————————
0 | 1 3 4 6 7 8 11 12 13 14 10 16 17 18 19 20 10 16 17 18 19 20
1 | 0 2 0 5 2 0 9 5 2 0 21 15 9 5 2 0 21 15 9 5 2 0
Remark: Parts 3 and 4 renumber the states. If you want your new numbers to match the sample outputs exactly, note the renumbering schemes used here. In Part 3 (remove inaccessible states), the reachable states are numbered sequentially in the sorted order of their old numbers. In Part 4, the groups are numbered sequentially in the sorted order of the smallest states in the groups. It is, of course, assumed that you follow the subset-numbering scheme specified in Part 1. If you use different numbering schemes, you would get isomorphic DFA, and these isomorphisms can be manually verified for correctness.

Submit a single C/C++ file. Do not use global/static variables. Do not use STL data types.