(* the function f *)
fun f xs =
let fun h(us, []) = Set.empty
| h(us, vs) =
if Str.prefix(Str.fromString "000", vs)
then StrSet.union(Set.sing(rev us), h(hd vs :: us, tl vs))
else h(hd vs :: us, tl vs)
in h([], xs) end;
(* the function g *)
fun g xs = Set.size(f xs);
(* test for being an element of the language X *)
fun in_X xs = g xs mod 2 = 0;
(* if n >= 0, upto n returns the set of all strings of 0s and 1s of
length <= n *)
fun upto 0 = StrSet.fromString "%"
| upto n =
StrSet.union
(StrSet.power(StrSet.fromString "0, 1", n),
upto(n - 1));
(* if n >= 0, boundedTest n dfa assesses dfa using all test data of
length <= n *)
fun boundedTest n dfa =
let val alls = upto n
val goods = Set.filter in_X alls
val bads = StrSet.minus(alls, goods)
val acc = DFA.accepted dfa
val notAcc = not o acc
in Set.all acc goods andalso Set.all notAcc bads end;
(* test dfa assesses dfa using all test data of length <= 20 *)
val test = boundedTest 20;