[artemis_f]

This is homework. Before this I have myself managed to create a NFA to DFA converter in Java and then something that can take a string and say if the dfa can accept string or not for some other assignment. However for PDAs I am stuck because I do not know how to deal with the non determinism.

I am trying to create my program using Java. The program is given a string and a PDA (specified in the structure written in lines in a file where each line is like the following:
currentState inputSymbolToBeConsumed SymbolAtTopOfStack ResultingState StringWhichReplacesTopOfStack

Since PDA is non deterministic a state can have more than one transition to another state and the program has to explore multiple paths simultaneously. But it should only explore a path until a set number of transitions and if it can't then that path should be abandoned.

What I need is for someone to explain to me what type of methods I am going to need:
So far I have the following methods:
In a Reader class:
getAcceptingState (reads final states into a data structure)
getStartingState (reads startiing states into a data structure)
getTransitions (which reads all transitions into an ArrayList<String[]> so I can access the various elements)

In the PDA class:
public ArrayList<String> getTransitionState(String filename, String inputSymbol, String inputState, Stack stack)
[this returns all the states a state will transition to]

public ArrayList<String> getTransitionStack(String filename, String inputSymbol, String inputState, String inputStack)
[this one notes all the StringWhichReplacesTopOfStack for each transitioned to state. The first string is seperated by the other one with a *** so basically I can extract the info I want though it is not ideal]

public Stack modifyTheStack(String filename, String alph, String stateIs, Stack stackIs){
[this takes the current stack and modifies it based on the current state. I am not sure I have the rules correct so I shall post here so someone can tell me if I am wrong]

public Stack modifyTheStack(String filename, String alph, String stateIs, Stack stackIs){
		
	String stackTopIs = stackIs.peek().toString();
	ArrayList<String> stackWillBe = getTransitionStack(filename, alph, stateIs, stackTopIs);
		
	//for s(q,a,X)->(p,y) if y=EPSILON then pop stack
	if (stackWillBe.contains("EPSILON")){
		stackIs.pop();
		System.out.println("if (stackWillBe.contains(EPSILON) popstackIs: " + stackIs);
	}
	//if y=X stack is unchanged
	String stackStrTemp = stackWillBe.get(0);
	if ((stackWillBe.size()==1)&&(stackStrTemp==stackTopIs)){
			System.out.println("if ((stackWillBe.size()==1)&&(stackStrTemp==stackTopIs)):do noth ");//do nothing
	}
		
	Stack stackIsTemp = new Stack();	
	//if y = YZ then X is replaced by Z and Y is pushed on stack
	if (stackWillBe.size()>=1){
		stackIs.pop();
		for (int sz=0; sz<stackWillBe.size(); sz++){
		//store in temp stack because elements being added in reverse order
				stackIsTemp.add(stackWillBe.get(sz));	
		}
			
		//if X is empty then push y
		if (stackTopIs=="EPSILON"){
			for(int s=0; s<stackIsTemp.size(); s++){
			stackIs.add(stackIsTemp.pop().toString());
			}
		}
		else{
			//new stack top is meant to be Y
			for(int s=0; s<stackIsTemp.size(); s++){
			stackIs.add(stackIsTemp.pop().toString());
			}
		}
	}//end if stack is > 1
		
		 return stackIs;
}

And finally I have
public ArrayList<String> epsilonTransition(String filename, String inputState, Stack stackIs)
Which returns stateThenStackSymbols so I can basically extract the info I need from it.

What I really, really, need to know now is If I have gone off in completely the wrong direction? If I have how can I get back on the right track. If I am on the right track then how can I bring this all together to actually implement the recursion this program obviously needs? Could someone explain what type of methods I need to create and what they should be doing?

I would be really really greatful for any insight you can give me. I have scoured heaps of internet sites and not found anything to help me I'm afraid.

Let me know if you actually need to see all the rest of my code to help me.