Derek Elder: +Program

2009-11-02T23:04:10Z

+Program

New page

<pre>
//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);
}
}
</pre>

Directory:Derek Elder/Programs/NonDeterministicFiniteAutomata - Revision history

Derek Elder: +Program