217 lines
6.7 KiB
Java
217 lines
6.7 KiB
Java
import java.io.BufferedReader;
|
|
import java.io.FileReader;
|
|
import java.io.IOException;
|
|
|
|
/**
|
|
* @author Andrew Coleman
|
|
* Provides a Java implementation for a deterministic finite automata with the ability to minimize a machine.
|
|
*/
|
|
public class DFA {
|
|
|
|
private int numstates, numterminals, numfinalstates;
|
|
private char terminals[];
|
|
private int path[][];
|
|
private boolean finalstates[];
|
|
|
|
// constructs a new DFA object from a file as per the in class specs
|
|
/*
|
|
* format of the input file:
|
|
* IntegerN - the number of terminal characters in the machine
|
|
* Terminal * N - all of the terminals separated by a space
|
|
* NumStates - number of states in the machine
|
|
* - next is NumStates * IntegerN rows of transitions
|
|
* StartState TerminalTransitionChar EndState
|
|
* NumFinalStates - number of final states
|
|
* FinalStates - the final states of the machine separated by spaces
|
|
*
|
|
* Check the minmachine.txt file for a complete minimizable example.
|
|
*/
|
|
DFA ( String filename ) {
|
|
BufferedReader infile = null;
|
|
numstates = 0;
|
|
numterminals = 0;
|
|
try {
|
|
infile = new BufferedReader ( new FileReader ( filename ) );
|
|
|
|
numterminals = Integer.parseInt ( infile.readLine() );
|
|
String strterms[] = infile.readLine().split ( " " );
|
|
terminals = new char[numterminals];
|
|
for ( int slen = 0; slen < numterminals; slen++ ) {
|
|
terminals[slen] = strterms[slen].charAt ( 0 );
|
|
}
|
|
|
|
numstates = Integer.parseInt ( infile.readLine() );
|
|
|
|
path = new int[numstates][numterminals];
|
|
for ( int i = 0; i < (numstates * numterminals); i++ ) {
|
|
String pathstr[] = infile.readLine().split ( " " );
|
|
int first = Integer.parseInt ( pathstr[0] );
|
|
int second = Integer.parseInt ( pathstr[2] );
|
|
for ( int t = 0; t < numterminals; t ++ ) {
|
|
if ( terminals[t] == pathstr[1].charAt ( 0 ) ) {
|
|
path[first][t] = second;
|
|
break;
|
|
}
|
|
}
|
|
}
|
|
|
|
numfinalstates = Integer.parseInt ( infile.readLine() );
|
|
finalstates = new boolean[numstates];
|
|
String[] fs = infile.readLine().trim().split ( " " );
|
|
for ( int tmp = 0; tmp < numfinalstates; tmp++ ) {
|
|
finalstates[Integer.parseInt ( fs[tmp] )] = true;
|
|
}
|
|
|
|
infile.close();
|
|
}
|
|
catch ( IOException exception ) {
|
|
exception.printStackTrace();
|
|
}
|
|
catch ( Exception exception ) {
|
|
System.out.println ( "Malformed input file!" );
|
|
exception.printStackTrace();
|
|
}
|
|
}
|
|
|
|
// returns a string that is compatible with our input file specification
|
|
public String toString() {
|
|
StringBuffer buf = new StringBuffer();
|
|
buf.append ( numterminals + "\n" );
|
|
for ( int i = 0; i < numterminals; i++ )
|
|
buf.append ( terminals[i] + " " );
|
|
buf.deleteCharAt ( buf.length() - 1 );
|
|
buf.append ( "\n" + numstates + "\n" );
|
|
for ( int i = 0; i < numstates; i++ ) {
|
|
for ( int j = 0; j < numterminals; j++ ) {
|
|
buf.append ( i + " " + terminals[j] + " " + path[i][j] + "\n" );
|
|
}
|
|
}
|
|
buf.append ( numfinalstates + "\n" );
|
|
for ( int i = 0; i < numstates; i++ )
|
|
if ( finalstates[i] == true )
|
|
buf.append ( i + " " );
|
|
buf.deleteCharAt ( buf.length() - 1 );
|
|
return buf.toString();
|
|
}
|
|
|
|
public void minimize() {
|
|
// distinguishable marks
|
|
boolean mark[][] = new boolean[numstates][numstates];
|
|
// the list of reachable states
|
|
boolean reachable[] = new boolean[numstates];
|
|
// a flag for various uses throughout the method
|
|
boolean flag = true;
|
|
|
|
// remove all unreachable states from consideration altogether
|
|
// assuming we can always reach q0
|
|
reachable[0] = true;
|
|
boolean visited[] = new boolean[numstates];
|
|
// queue-less bfs!
|
|
while ( flag ) {
|
|
flag = false;
|
|
for ( int state = 0; state < numstates; state++ ) {
|
|
if ( reachable[state] && !visited[state] ) {
|
|
visited[state] = true;
|
|
flag = true;
|
|
for ( int term = 0; term < numterminals; term++ ) {
|
|
reachable[ path[state][term] ] = true;
|
|
}
|
|
}// end if
|
|
}// endfor state
|
|
}// end while
|
|
|
|
// find all pairs of states (p,q) such that final[p] != final[q]
|
|
for ( int statenum = 0; statenum < numstates; statenum++ ) {
|
|
if ( !reachable[statenum] ) continue;
|
|
for ( int statenum2 = 0; statenum2 < numstates; statenum2++ ) {
|
|
if ( !reachable[statenum2] ) continue;
|
|
if ( finalstates[statenum] != finalstates[statenum2] )
|
|
mark[statenum][statenum2] = true;
|
|
else
|
|
mark[statenum][statenum2] = false;
|
|
}
|
|
}
|
|
|
|
// find all pairs (p,q) and mark them as distinguishable
|
|
// i am looking at path[p] foreach terminal and path[q], if both
|
|
// states are distinct, then mark these
|
|
flag = true;
|
|
// continue until no mark has been made
|
|
while ( flag ) {
|
|
flag = false;
|
|
for ( int x = 0; x < numstates; x++ ) {
|
|
if ( !reachable[x] ) continue;
|
|
for ( int y = 0; y < numstates; y++ ) {
|
|
if ( x == y ) continue;
|
|
for ( int t = 0; t < numterminals; t++ ) {
|
|
if ( mark[ path[x][t] ][ path[y][t] ] && !mark[x][y] ) {
|
|
mark[x][y] = true;
|
|
flag = true;
|
|
}
|
|
}// end terminal
|
|
}// endfor second state
|
|
}// endfor first state
|
|
}// end while
|
|
|
|
int minstates[] = new int[numstates];
|
|
for ( int state = 0; state < numstates; state++ ) {
|
|
visited[state] = false;
|
|
if ( !reachable[state] )
|
|
minstates[state] = -1;
|
|
else
|
|
minstates[state] = state;
|
|
}
|
|
|
|
// extract the distinguishable states
|
|
for ( int state = 0; state < numstates; state++ ) {
|
|
if ( minstates[state] == -1 || visited[state] ) continue;
|
|
for ( int p = 0; p < numstates; p++ ) {
|
|
if ( p == state || minstates[p] == -1 ) continue;
|
|
if ( !mark[state][p] && !visited[p] ) {
|
|
minstates[p] = state;
|
|
visited[p] = true;
|
|
}
|
|
}// endfor p
|
|
}// endfor state
|
|
|
|
// set minstate to have all of the new minimized state numbers
|
|
int unique = 0;
|
|
for ( int x = 0; x < minstates.length; x++ ) {
|
|
if ( minstates[x] == x && minstates[x] != -1 ) {
|
|
for ( int y = 0; y < minstates.length; y++ ) {
|
|
if ( minstates[y] == x ) {
|
|
minstates[y] = unique;
|
|
}
|
|
}
|
|
unique++;
|
|
}
|
|
}
|
|
|
|
// rearrange all the paths using the minstate array into a new path array
|
|
int newpath[][] = new int[numstates][numterminals];
|
|
boolean newfinal[] = new boolean[numstates];
|
|
int minstatecounter = 0, minfinalcounter = 0;
|
|
for ( int state = 0; state < numstates; state++ ) {
|
|
// find all accessible vertecies and vertecies that have not been counted already
|
|
if ( minstates[state] != -1 && minstatecounter <= minstates[state] ) {
|
|
for ( int t = 0; t < numterminals; t++ ) {
|
|
newpath[minstatecounter][t] = minstates[ path[state][t] ];
|
|
}
|
|
if ( finalstates[state] ) {
|
|
newfinal[minstatecounter] = true;
|
|
minfinalcounter++;
|
|
}
|
|
else {
|
|
newfinal[minstatecounter] = false;
|
|
}
|
|
minstatecounter++;
|
|
}
|
|
}
|
|
|
|
path = newpath;
|
|
numstates = minstatecounter;
|
|
numfinalstates = minfinalcounter;
|
|
finalstates = newfinal;
|
|
}
|
|
}
|