/** * Computes the Lambda-closure * of the given state set. [Martin, Def. 3.13] * @param set set of {@link State} objects * @return set of {@link State} objects (the input set is unmodified) */ public Set lambdaClosure(Set set) { Set res = new HashSet(); // contains the states that are in the closure and have been visited Set pending = new HashSet(); // contains the states that are in the closure but have not yet been visited pending.addAll(set); while (!pending.isEmpty()) { State q = pending.iterator().next(); pending.remove(q); res.add(q); Set s = new HashSet(delta(q, LAMBDA)); s.removeAll(res); pending.addAll(s); } return res; } /** * Performs transitions in extended transition function. [Martin, Def. 3.14] * @return delta*(q,s) * @exception IllegalArgumentException if a symbol in s is not in the alphabet */ public Set deltaStar(State q, String s) throws IllegalArgumentException { Set set = new HashSet(); set.add(q); set = lambdaClosure(set); for (char c : s.toCharArray()) { Set nset = new HashSet(); for (State p : set) nset.addAll(delta(p, c)); set = lambdaClosure(nset); } return set; }