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!

Do you have any specific java programming questions?
Is your problem with designing an algorithm to solve a problem
Or do you have a design/algorithm and need help writing the java code for it?

I kinda have an algorithm, I just can't seem to implement. What's on the screen right now is basically my consolation algorithm (and I can't even get that to work). The algorithm I'm trying to implement is:

mark first node as visited
for each unvisited node that has an epsilon transition from the root
get adjacent nodes with an epsilon transition
add them to eclosure, mark them as visited
if they appeared previously, do not add them to eclosure again
return eclosure

So this is most a logic problem. You have a complicated program that needs to be debugged to find why is doesn't do what you want it to do.

For most of my debugging I use print outs of data to show how variables change and how the execution flow goes. Keep adding print outs to show the data and compare what is printed with what you expect the values to be.
Also desk checking with paper and pencil can be used to work out details of complicated logic.

thats what ive been doing. i was looking for a fresh perspective on the algorithm, i find that when i look at other peoples code i can sometimes see stupid errors or flaws in logic that the original programmer see

This article has been dead for over six months. Start a new discussion instead.