Directory:Derek Elder/Programs/NonDeterministicFiniteAutomata

< Directory:Derek Elder‎ | Programs
Revision as of 23:04, 2 November 2009 by Derek Elder (talk | contribs) (+Program)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
//Program 1e
//Professor Pattis, ICS-23 Lab 1
//Programmers: Cameron Ruatta, Derek Elder

import edu.uci.ics.pattis.introlib.Prompt;
import edu.uci.ics.pattis.introlib.TypedBufferReader;
import edu.uci.ics.pattis.ics23.collections.*;

import java.util.Iterator;
import java.util.StringTokenizer;
import java.io.EOFException;

public class NDFA
{
	public static void main(String[] args)
	{
		Map<String,Map<String,Set<String>>> nonDeterministicMap = new ArrayMap<String,Map<String,Set<String>>>();
		TypedBufferReader tbr = new TypedBufferReader("Enter Non-Deterministic Finite Automaton Description File");
		
		for(;;)
		{
			try
			{
				String line = tbr.readLine();
				StringTokenizer st = new StringTokenizer(line, ";");
				String initialState = st.nextToken();
				
				if(!st.hasMoreTokens())
				{
					Map<String,Set<String>> stateMap = nonDeterministicMap.get(initialState);
					stateMap = new ArrayMap<String,Set<String>>();
					nonDeterministicMap.put(initialState,stateMap);
				}
				while(st.hasMoreTokens())
				{
					String token = st.nextToken();
					String token2 = st.nextToken();
					Set<String> transitions = new ArraySet<String>();

					//Update map
					Map<String,Set<String>> stateMap = nonDeterministicMap.get(initialState);
					if(stateMap == null)
					{
						stateMap = new ArrayMap<String,Set<String>>();
						nonDeterministicMap.put(initialState,stateMap);
					}			
					 //If the token has a state associated with it already, add it in
					if(stateMap.get(token) != null)
					{
						Iterator<String> it = stateMap.get(token).iterator();
						while(it.hasNext())
							transitions.add(it.next());
					}
					transitions.add(token2);
					stateMap.put(token,transitions);
				}
			} catch(EOFException e) {break;}
		}

		System.out.println("Non-Deterministic Finite Automaton");
		List<String> stateList = new ArrayList<String>(nonDeterministicMap.keys());
		Collections.sort(stateList);
		for(String states : stateList)
		{
			Map<String,Set<String>> keys = nonDeterministicMap.get(states);
			System.out.println(states + " transitions = " + keys);
		}
		
		tbr = new TypedBufferReader("Enter start state/inputs file");
		for(;;)
		{
			try
			{
				String line = tbr.readLine();
				StringTokenizer st = new StringTokenizer(line, ";");
				String initialToken = st.nextToken();
				initialStates.add(initialToken);
				Set<String> currentStates = new ArraySet<String>();
				currentStates.add(st.nextToken());
				
				System.out.println("Initial state(s) = " + currentStates);
				while(st.hasMoreTokens())
				{
					String token = st.nextToken();
					Set<String> intermediateStates = new ArraySet<String>();
					
					for(String state : currentStates)
					{
						Set<String> toStates = nonDeterministicMap.get(state).get(token);
						if (toStates != null)
							intermediateStates.addAll(toStates);
					}
					currentStates = nextStates;
					System.out.println("input = " + token + "; new possible states = " + currentStates);
				}
			} catch(EOFException e) {break;}
		}
		System.out.println("Final possible state(s) = " + currentStates);
	}
}