I can't believe I'm asking this, but this assignment I was given is proving very difficult. I was asked to find the ECLOSE function of a given Epsilon non-deterministic finite automata. All it is is the BFS tree of a graph from a given point, provided that the vertices are connected by an epsilon edge.
The weird thing about it is that my instructor is using an ArrayList instead of a Linked List or Queue for her graph representation, which I don't like. I feel like I'm almost there as far as solving the problem, I would really appreciate a push in the right direction, however.
The eclose(int i) method is the one I'm supposed to be working on. I also made the getNeighbors(State s) method to help.
The
#
System.out.println("Size: "+eclosure.size());
#
for(int x = 0; x < eclosure.size(); x++)
#
System.out.println(eclosure.get(x));part is just for me to see where I'm at as far as correctness.
import java.util.*;
class ENFA{
private int stateNum; //number of states
private State[] states; // array of states
//Create e-NFA with 5 states, state 4 is the accepting state
public ENFA(){
stateNum = 5;//number of states
states = new State[stateNum];
ArrayList<Integer> A, B, E;
for(int i=0; i<stateNum; i++){
states[i] = new State();
A = states[i].deltaA;
B = states[i].deltaB;
E = states[i].deltaE;
A.add((i+1)%stateNum);
A.add((i+2)%stateNum);
B.add((i+2)%stateNum);
if(i == 2){
B.add(0);
}
if(i == 0 || i== 2){
E.add((i+1)%stateNum);
}
if(i==0 || i==4){
E.add((i+4)%stateNum);
}
if(i == 1){
E.add(3);
}
}
states[stateNum-1].accepting = true;
}
//Randomly creates an e-NFA with size the specified parameter
public ENFA(int stateNum){
this.stateNum = stateNum;
states = new State[stateNum];
for(int i=0; i<stateNum; i++){
states[i] = new State();
ArrayList<Integer> A = states[i].deltaA;
ArrayList<Integer> B = states[i].deltaB;
ArrayList<Integer> E = states[i].deltaE;
//Create transitions from state i to some states.
for(int j = 0; j<stateNum; j++){
double r1 = Math.random();
int r2 = (int)(Math.random()*stateNum);
if(r1>0.95){
if(!E.contains(r2))
E.add(r2);
}else if(r1>0.8){
if(!A.contains(r2))
A.add(r2);
}else if(r1 > 0.65){
if(!B.contains(r2))
B.add(r2);
}
}
}
states[stateNum-1].accepting = true;
}
//Display this e-NFA
public void display(){
int stateNum = states.length;
for(int i=0; i<stateNum; i++){
System.out.println("-----------------------------------------");
System.out.println(i +": ");
System.out.print("\na-transitions: ");
display(states[i].deltaA);
System.out.print("\nb-transitions: ");
display(states[i].deltaB);
System.out.print("\ne-transitions: ");
display(states[i].deltaE);
}
}
//Display the specified array
public void display(ArrayList<Integer> array){
Iterator<Integer> iter = array.iterator();
while(iter.hasNext()){
System.out.print(iter.next() + ", ");
}
System.out.println();
}
//Return the size of this e-NFA
public int size(){
return stateNum;
}
//Compute the eclosure of state i and return it
public ArrayList<Integer> eclose(int i){
int count = 0;
ArrayList<Integer> eclosure = new ArrayList<Integer>();
if(!states[i].visited==true)
{
eclosure.add(i);
states[i].visited=true;
}
for(int v = i; v < states.length; v++)
{
ArrayList<Integer> n = getNeighbors(states[v]);
for(int w = 0; w < n.size(); w++)
for(int z = 0; z < eclosure.size(); z++)
{
if(n.get(w) != eclosure.get(z))
{
count++;
if(z == eclosure.size());
{
eclosure.add(n.get(w));
count = 0;
}
}
}
n.clear();
}
System.out.println("Size: "+eclosure.size());
for(int x = 0; x < eclosure.size(); x++)
System.out.println(eclosure.get(x));
return eclosure;
}
//helper method, gets all nodes that have an epsilon transition from s
public ArrayList<Integer> getNeighbors(State s)
{
ArrayList<Integer> neighbors = new ArrayList<Integer>();
if(!s.deltaE.isEmpty())
for( int i = 0; i<s.deltaE.size(); i++)
neighbors.add(s.deltaE.get(i));
return neighbors;
}
//Is w a member of L? (Don't have to do it now)
public boolean member(String w){
return false;
}
}Here's a basic "state" class
import java.util.*;
class State{
ArrayList<Integer> deltaA; //a-transitions
ArrayList<Integer> deltaB; // b-transitions
ArrayList<Integer> deltaE; //epsilon-transitions
boolean accepting;//Is this state an accepting state?
boolean visited;//has this state been visited?
public State(){
deltaA = new ArrayList<Integer>();
deltaB = new ArrayList<Integer>();
deltaE = new ArrayList<Integer>();
accepting = false;
visited = false;
}
}and finally, the client program
import java.util.*;
//Create an E-NFA to accept a regular language over {a, b}
class ENFAtest{
public static void main(String[] args){
ENFA fa = new ENFA();
//ENFA fa = new ENFA(10); //test with other e-NFA's too.
//Display the e-NFA
fa.display();
//Compute ECLOSE for each state
System.out.println("\nCompute ECLOSE for each state");
for(int i=0; i<fa.size(); i++){
ArrayList<Integer> eclosure = fa.eclose(i);
System.out.print("ECLOSE("+i+") is " );
fa.display(eclosure);
}
}
}Any help would be appreciated. Thanks!