96
LAMPIRAN 1 Listing Program FAAlphabet.java package edu.usfca.vas.machine.fa; import edu.usfca.vas.app.Preferences; import edu.usfca.xj.foundation.XJXMLSerializable; import java.util.Iterator; import java.util.LinkedHashSet; import java.util.Set; public class FAAlphabet implements XJXMLSerializable { protected Set symbols = new LinkedHashSet(); protected transient FAMachine machine = null; public void setMachine(FAMachine machine) { this.machine = machine; } public void setSymbolsString(String s) { symbols.clear(); for(int c=0; c<s.length(); c++) symbols.add(String.valueOf(s.charAt(c))); } public String getSymbolsString() { String s = ""; Iterator iterator = symbols.iterator(); while(iterator.hasNext()) { s += iterator.next(); } return s; }
97
public void addSymbol(String s) { symbols.add(s); } public void setSymbols(Set symbols) { this.symbols = symbols; } public Set getSymbols() { if(machine != null && machine.getType() == FAMachine.MACHINE_TYPE_NFA) symbols.add(Preferences.getEpsilonTransition()); return symbols; } }
98
FAMachine.java package edu.usfca.vas.machine.fa; import edu.usfca.xj.foundation.XJXMLSerializable; import java.util.HashSet; import java.util.Iterator; import java.util.List; import java.util.Set; public class FAMachine implements XJXMLSerializable { public static final int MACHINE_TYPE_DFA = 0; public static final int MACHINE_TYPE_NFA = 1; protected FAStates states = new FAStates(); protected FAAlphabet alphabet = new FAAlphabet(); protected FATransitions transitions = new FATransitions(); protected Set stateSet; protected int type = MACHINE_TYPE_DFA; protected transient String debugString; protected transient String debugLastSymbol; public FAMachine() { init(); } public FAMachine(Set statesSet, Set transitionsSet, String startState, List finalStates) { init(); addState(statesSet, startState, finalStates); addTransitions(transitionsSet); } public void init() { alphabet.setMachine(this); alphabet.setSymbolsString("01"); stateSet = new HashSet(); }
99
public void setStates(FAStates states) { this.states = states; } public FAStates getStates() { return states; } public void setAlphabet(FAAlphabet alphabet) { this.alphabet = alphabet; alphabet.setMachine(this); } public FAAlphabet getAlphabet() { return alphabet; } public void setTransitions(FATransitions transitions) { this.transitions = transitions; } public FATransitions getTransitions() { return transitions; } public void addState(FAState s) { states.addState(s); } public void addState(Set set, String startState, List finalStates) { Iterator iterator = set.iterator(); while(iterator.hasNext()) { Set stateSet = (HashSet)iterator.next(); FAState state = new FAState(stateSet.toString()); for(int f=0; f
100
if(stateSet.contains(finalStates.get(f))) { state.accepted = true; break; } } if(state.name.equals(startState)) state.start = true; addState(state); } } public void removeState(FAState s) { states.removeState(s); transitions.removeState(s.name); } public void renameState(FAState s, String oldName, String newName) { s.name = newName; transitions.renameState(oldName, newName); } public boolean containsStateName(String name) { return states.contains(name); } public List getStateList() { return states.getStates(); } public List getStateNames() { return states.getStateNames(); } public void setType(int type) { this.type = type; } public int getType() {
101
return type; } public void setSymbolsString(String s) { alphabet.setSymbolsString(s); } public String getSymbolsString() { return alphabet.getSymbolsString(); } public void addSymbol(String s) { alphabet.addSymbol(s); } public Set getSymbols() { return alphabet.getSymbols(); } public void addTransitionPattern(String s1, String pattern, String s2) { transitions.addTransitionPattern(s1, pattern, s2); } public boolean containsTransition(String s1, String symbol, String s2) { return transitions.containsTransition(s1, symbol, s2); } public void addTransitions(Set set) { Iterator iterator = set.iterator(); while(iterator.hasNext()) { transitions.addTransition((FATransition)iterator.next()); } } public void removeTransitionPattern(String s1, String pattern, String s2) { for(int i=0; i<pattern.length(); i++) transitions.removeTransition(s1, pattern.substring(i, i+1), s2); }
102
public void clear() { states.clear(); transitions.clear(); } public String check() { if(type == MACHINE_TYPE_DFA) { String error = states.check(); if(error != null) return error; error = transitions.check(alphabet.getSymbols().size(), states); if(error != null) return error; } return null; } public boolean accept(String s) { reset(); stateSet = getStartStates(); for(int i=0; i<s.length(); i++) { put(s.charAt(i)); } return isAcceptedState(stateSet); } public boolean isAccepting() { return isAcceptedState(stateSet); } public void setStateSet(Set stateSet) { this.stateSet = stateSet; } public Set getStateSet() { return stateSet; }
103
public Set getLastTransitionSet() { return getTransitions().getLastTransitionSet(); } public Set getStartStates() { return transitions.getEpsilonClosureStateSet(states.getStartState()); } public Set getNextStateSet(Set stateSet, String symbol) { return getStateSet(stateSet, symbol); } public boolean isAcceptedState(String state) { return states.isAccepted(state); } public boolean isAcceptedState(Set stateSet) { return states.isAccepted(stateSet); } // *** Conversion public FAMachine convertNFA2DFA() { Set dfaStatesSet = new HashSet(); Set transitionsSet = new HashSet(); String startState = states.getStartState(); Set startSet = new HashSet(); startSet.add(startState); dfaStatesSet.add(startSet); recursiveBuildDFA(startSet, dfaStatesSet, transitionsSet); return new FAMachine(dfaStatesSet, transitionsSet, startSet.toString(), states.getFinalStates()); } public void recursiveBuildDFA(Set statesSet, Set dfaStatesSet, Set transitionsSet) { Iterator iterator = alphabet.getSymbols().iterator();
104
while(iterator.hasNext()) { String symbol = (String)iterator.next(); Set newSet = getStateSet(statesSet, symbol); if(newSet.size()>0) transitionsSet.add(new FATransition(statesSet.toString(), symbol, newSet.toString())); if(!dfaStatesSet.contains(newSet) && newSet.size()>0) { dfaStatesSet.add(newSet); recursiveBuildDFA(newSet, dfaStatesSet, transitionsSet); } } } public Set getStateSet(Set statesSet, String symbol) { Set newStateSet = new HashSet(); Iterator iterator = statesSet.iterator(); while(iterator.hasNext()) { String state = (String)iterator.next(); Set set = transitions.getClosureStateSet(state, symbol); if(set.size()>0) newStateSet.addAll(set); } return newStateSet; } // *** Debug methods public void debugReset(String s) { reset(); debugString = s; } public boolean debugStepForward() { if(debugString.length() == 0) return false; if(stateSet.isEmpty()) stateSet = getStartStates();
105
transitions.getLastTransitionSet().clear(); put(debugString.charAt(0)); debugLastSymbol = debugString.substring(0, 1); debugString = debugString.substring(1); if(stateSet.isEmpty()) return false; else return debugString.length() > 0; } public String debugLastSymbol() { return debugLastSymbol; } public String debugString() { return debugString; } public String toString() { String s = "Description of the machine:\n"; s += states; s += transitions; return s; } // *** Processing methods public void reset() { stateSet.clear(); transitions.getLastTransitionSet().clear(); debugLastSymbol = ""; } public void put(char c) { stateSet = getNextStateSet(stateSet, String.valueOf(c)); } }
106
FAState.java package edu.usfca.vas.machine.fa; import edu.usfca.xj.foundation.XJXMLSerializable; public class FAState implements XJXMLSerializable { public String name = null; public boolean start = false; public boolean accepted = false; public static FAState createState(String name) { return new FAState(name); } public static FAState createStartState(String name) { return new FAState(name, true, false); } public static FAState createAcceptedState(String name) { return new FAState(name, false, true); } public FAState() {} public FAState(String name) { this.name = name; } public FAState(String name, boolean start, boolean accepted) { this.name = name; this.start = start; this.accepted = accepted; } public String getName() { return name; }
107
public void setName(String name) { this.name = name; } public boolean isStart() { return start; } public void setStart(boolean start) { this.start = start; } public boolean isAccepted() { return accepted; } public void setAccepted(boolean accepted) { this.accepted = accepted; } public String toString() { String s = ""; s += "< name = "+name+">"; s += "< start = "+start+">"; s += "< accepted = "+accepted+">"; return s; } }
108
FAStates.java package edu.usfca.vas.machine.fa; import edu.usfca.vas.app.Localized; import edu.usfca.xj.foundation.XJXMLSerializable; import java.util.ArrayList; import java.util.Iterator; import java.util.List; import java.util.Set; public class FAStates implements XJXMLSerializable { protected List states = new ArrayList(); public FAStates() {} public void addState(FAState s) { states.add(s); } public void removeState(FAState s) { states.remove(s); } public void setStates(List states) { this.states = states; } public List getStates() { return states; } public ArrayList getStateNames() { ArrayList names = new ArrayList(); for(int i=0; i<states.size(); i++) { FAState wrapper = (FAState)states.get(i); names.add(wrapper.name);
109
} return names; } public boolean contains(String name) { for(int i=0; i<states.size(); i++) { FAState wrapper = (FAState)states.get(i); if(wrapper.name.equals(name)) return true; } return false; } public void clear() { states.clear(); } public int numberOfStartStates() { int count = 0; for(int i=0; i<states.size(); i++) { FAState wrapper = (FAState)states.get(i); if(wrapper.start) count++; } return count; } public int numberOfAcceptedStates() { int count = 0; for(int i=0; i<states.size(); i++) { FAState wrapper = (FAState)states.get(i); if(wrapper.accepted) count++; } return count; } public String check() { if(numberOfAcceptedStates() == 0)
110
return Localized.getString("faNoAcceptedState"); if(numberOfStartStates() == 0) return Localized.getString("faNoStartState"); if(numberOfStartStates() > 1) return Localized.getString("faMultipleStartStates"); return null; } public String getStartState() { for(int i=0; i<states.size(); i++) { FAState wrapper = (FAState)states.get(i); if(wrapper.start) return wrapper.name; } return null; } public List getFinalStates() { List finalStates = new ArrayList(); for(int i=0; i<states.size(); i++) { FAState wrapper = (FAState)states.get(i); if(wrapper.accepted) finalStates.add(wrapper.name); } return finalStates; } public boolean isAccepted(String state) { for(int i=0; i<states.size(); i++) { FAState wrapper = (FAState)states.get(i); if(wrapper.name.equals(state)) return wrapper.accepted; } return false; } public boolean isAccepted(Set stateSet) { Iterator iterator = stateSet.iterator(); while(iterator.hasNext()) {
111
if(isAccepted((String)iterator.next())) return true; } return false; } public String toString() { String s = "* states *\n"; for(int i=0; i<states.size(); i++) { FAState state = (FAState)states.get(i); s += state+"\n"; } return s; } }
112
FATransition.java package edu.usfca.vas.machine.fa; import edu.usfca.xj.foundation.XJXMLSerializable; public class FATransition implements XJXMLSerializable { public String s1; public String symbol; public String s2; public FATransition() {} public FATransition(String s1, String symbol, String s2) { this.s1 = s1; this.symbol = symbol; this.s2 = s2; } public String getS1() { return s1; } public void setS1(String s1) { this.s1 = s1; } public String getSymbol() { return symbol; } public void setSymbol(String symbol) { this.symbol = symbol; } public String getS2() { return s2; }
113
public void setS2(String s2) { this.s2 = s2; } public String toString() { return "<"+s1+", "+symbol+" -> "+s2+">"; } }
114
FATransitions.java package edu.usfca.vas.machine.fa; import edu.usfca.vas.app.Localized; import edu.usfca.vas.app.Preferences; import edu.usfca.vas.machine.Tool; import edu.usfca.xj.foundation.XJXMLSerializable; import java.util.*; public class FATransitions implements XJXMLSerializable { protected List transitions = new ArrayList(); protected transient Set lastTransitionSet = new HashSet(); public static transient String epsilonSymbol = null; public FATransitions() {} public String getEpsilonSymbol() { if(epsilonSymbol == null) return Preferences.getEpsilonTransition(); else return epsilonSymbol; } public void addTransitionPattern(String s1, String pattern, String s2) { Iterator iterator = Tool.symbolsInPattern(pattern).iterator(); while(iterator.hasNext()) addTransition(s1, (String)iterator.next(), s2); } public void addTransition(String s1, String symbol, String s2) { transitions.add(new FATransition(s1, symbol, s2)); } public void addTransition(FATransition transition) { transitions.add(transition); }
115
public boolean containsTransition(String s1, String symbol, String s2) { Iterator iterator = transitions.listIterator(); while(iterator.hasNext()) { FATransition w = (FATransition)iterator.next(); if(w.s1.equals(s1) && w.s2.equals(s2) && w.symbol.equals(symbol)) { return true; } } return false; } public void setTransitions(List transitions) { this.transitions = transitions; } public List getTransitions() { return transitions; } public void removeTransition(String s1, String symbol, String s2) { Iterator iterator = transitions.listIterator(); while(iterator.hasNext()) { FATransition w = (FATransition)iterator.next(); if(w.s1.equals(s1) && w.s2.equals(s2) && w.symbol.equals(symbol)) { transitions.remove(w); iterator = transitions.listIterator(); } } } public void removeState(String s) { Iterator iterator = transitions.listIterator(); while(iterator.hasNext()) { FATransition w = (FATransition)iterator.next(); if(w.s1.equals(s) || w.s2.equals(s)) { transitions.remove(w);
116
iterator = transitions.listIterator(); } } } public void renameState(String oldName, String newName) { Iterator iterator = transitions.listIterator(); while(iterator.hasNext()) { FATransition w = (FATransition)iterator.next(); if(w.s1.equals(oldName)) w.s1 = newName; if(w.s2.equals(oldName)) w.s2 = newName; } } public void clear() { transitions.clear(); } public int transitionCountForState(String s) { int count = 0; Iterator iterator = transitions.listIterator(); while(iterator.hasNext()) { FATransition w = (FATransition)iterator.next(); if(w.s1.equals(s)) count++; } return count; } public String check(int requiredNumberOfTransitions, FAStates states) { if(transitions.size() == 0) return Localized.getString("faNoTransition"); Iterator iterator = states.getStateNames().listIterator(); while(iterator.hasNext()) { String s = (String)iterator.next(); if(transitionCountForState(s) != requiredNumberOfTransitions) { Object[] args = { s, new Integer(requiredNumberOfTransitions) };
117
return Localized.getFormattedString("faStateNeedTransition", args); } } return null; } public Set getNextStateSet(String state, String symbol) { Set stateSet = new HashSet(); Iterator iterator = transitions.iterator(); while(iterator.hasNext()) { FATransition w = (FATransition)iterator.next(); if(w.s1.equals(state) && w.symbol.equals(symbol)) { lastTransitionSet.add(w); stateSet.add(w.s2); } } return stateSet; } public void epsilonClosureStateSet(String state, Set stateSet) { Iterator iterator = transitions.iterator(); while(iterator.hasNext()) { FATransition w = (FATransition)iterator.next(); if(w.s1.equals(state) && w.symbol.equals(getEpsilonSymbol())) { if(!stateSet.contains(w.s2)) { lastTransitionSet.add(w); stateSet.add(w.s2); epsilonClosureStateSet(w.s2, stateSet); } } } } public Set getEpsilonClosureStateSet(String state) { Set stateSet = new HashSet(); stateSet.add(state); epsilonClosureStateSet(state, stateSet); return stateSet; }
118
public Set getClosureStateSet(String state, String symbol) { Set stateSet = new HashSet(); Iterator iterator = transitions.iterator(); while(iterator.hasNext()) { FATransition w = (FATransition)iterator.next(); if(w.s1.equals(state) && w.symbol.equals(symbol)) { lastTransitionSet.add(w); stateSet.add(w.s2); epsilonClosureStateSet(w.s2, stateSet); } } return stateSet; } public Set getLastTransitionSet() { return lastTransitionSet; } public String toString() { String s = "* transitions *\n"; Iterator iterator = transitions.listIterator(); while(iterator.hasNext()) { FATransition w = (FATransition)iterator.next(); s += "<"+w.s1+", "+w.symbol+" -> "+w.s2+">\n"; } return s; } }
119
LAMPIRAN 2 Kuesioner Kuesioner Skripsi Sebelum Aplikasi Diuji 1. Manakah yang dibawah ini, menurut anda yang paling sukar ? a. Konstruksi DFA b. Konstruksi NFA 2. Pada nomor 1, bila anda menjawab “Konstruksi DFA”, apakah yang menjadi kesulitan anda ? a. Dalam membuat diagram transisi DFA b. Dalam melakukan transformasi ekspresi regular ke DFA c. Dalam melakukan transformasi DFA ke minimasi DFA d. Lainnya 3. Pada nomor 1, bila anda menjawab “Konstruksi NFA”, apakah yang menjadi kesulitan anda ? a. Dalam membuat diagram transisi NFA b. Dalam melakukan transformasi DFA ke NFA c. Dalam melakukan pengecekkan inputan string d. Lainnya 4. Apakah pembahasan yang dibuat dari Bina Nusantara University mengenai teori bahasa dan automata, khususnya DFA dan NFA dapat dimengerti ? a. Dapat dimengerti b. Cukup dimengerti c. Tidak dapat dimengerti
120
5. Apakah contoh yang diberikan dari Bina Nusantara University mengenai teori bahasa dan automata, khususnya DFA dan NFA sudah cukup untuk dimengerti ? a. Dapat dimengerti b. Cukup dimengerti c. Tidak dapat dimengerti 6. Menurut anda, sebaiknya slide dari Bina Nusantara University mengenai teori bahasa dan automata, khususnya DFA dan NFA perlu ditambahkan dengan apa ? a. Contoh yang lebih banyak b. Pembahasan yang lebih banyak c. Lainnya 7. Menurut anda, apakah slide dari Bina Nusantara University mengenai teori bahasa dan automata, khususnya DFA dan NFA menggunakan bahasa Inggris lebih baik ? a. Sangat baik b. Cukup baik c. Tidak perlu 8. Apakah anda mengalami kesulitan dalam membuat matriks transisi ? a. Ya b. Tidak 9. Apakah anda mengalami kesulitan dalam membuat diagram transisi ? a. Ya b. Tidak 10. Apakah anda mengalami kesulitan dalam menentukan 5-tuple apa ? a. Q = state b. ∑ = simbol input c. δ = fungsi transisi d. Lainnya
121
Kuesioner Skripsi Sesudah Aplikasi Diuji 1. Menurut Anda, apakah interface aplikasi ini sudah menarik ? a. Sangat setuju b. Setuju c. Tidak setuju d. Sangat tidak setuju 2. Menurut Anda, apakah aplikasi ini sudah sesuai dengan kebutuhan materi yang telah ditentukan dari Bina Nusantara University ? a. Sangat setuju b. Setuju c. Tidak setuju d. Sangat tidak setuju 3. Menurut Anda, apakah aplikasi ini sudah interaktif ? a. Sangat setuju b. Setuju c. Tidak setuju a. Sangat tidak setuju 4. Menurut Anda, apakah aplikasi ini mudah untuk digunakan ? a. Sangat setuju b. Setuju c. Tidak setuju d. Sangat tidak setuju 5. Menurut Anda, apakah aplikasi ini berguna untuk Anda dalam memahami DFA dan NFA ? a. Sangat setuju b. Setuju c. Tidak setuju d. Sangat tidak setuju
122
6. Menurut Anda, apakah aplikasi ini termasuk user friendly ? a. Sangat setuju b. Setuju c. Tidak setuju d. Sangat tidak setuju 7. Menurut Anda, apakah aplikasi ini memiliki running time yang cepat dalam melakukan eksekusi terhadap suatu intruksi ? a. Sangat setuju b. Setuju c. Tidak setuju d. Sangat tidak setuju 8. Bagaimana menurut Anda, jika ada suatu aplikasi yang mampu mengkonstruksi DFA dan NFA yang dapat membantu Anda dalam memahami DFA dan NFA ? a. Sangat tertarik b. Tertarik c. Biasa saja d. Tidak tertarik 9. Bagaimana menurut Anda, jika aplikasi ini dibuat dalam bentuk web ? a. Sangat baik b. Cukup baik c. Tidak perlu 10. Fitur apa saja yang ingin ditambahkan dalam aplikasi tersebut ?
123
