Determinism

A Term in FAIR format is backed by an automaton. That automaton can be deterministic or non-deterministic.

• Deterministic: for any state and any input character, there is at most one possible transition.
• Non-deterministic: a state may have several possible transitions for the same character.

Both kinds of automaton represent the same languages and work with every operation. The difference only matters when you need a stable order for the strings of a language.

Why it matters

Generating strings from a Term returns them in the order the automaton produces them. With a non-deterministic automaton, that order is not guaranteed to stay the same between calls.

This is only a problem when you paginate with an offset. If you generate strings 0-9, then 10-19, the two calls must use the same ordering, otherwise some strings may be skipped or repeated.

Checking determinism

The client lets you check whether a Term's automaton is deterministic. A Term created from a regex pattern is always reported as not deterministic, since it has no automaton yet.

Code
RegexSolverClient client = RegexSolverClient.builder()
    .apiToken(System.getenv("REGEXSOLVER_API_TOKEN"))
    .build();

Term term = Term.regex("(abc|de){2}");

boolean deterministic = client.isDeterministic(term);
System.out.println(deterministic); // false

Making a Term deterministic

The client can also return a new Term in FAIR format, backed by a deterministic automaton for the same language. Do this once, then reuse the resulting Term for all paginated string generation calls.

Code
RegexSolverClient client = RegexSolverClient.builder()
    .apiToken(System.getenv("REGEXSOLVER_API_TOKEN"))
    .build();

Term term = Term.regex("(abc|de){2}");

Term deterministicTerm = client.determinize(term);

// Safe to paginate now
List<String> page1 = client.generateStrings(deterministicTerm, 10, 0);
List<String> page2 = client.generateStrings(deterministicTerm, 10, 10);

Requesting a deterministic result directly

Operations that return a Term accept a determinism option. When enabled, the returned FAIR is guaranteed to be deterministic, so there is no need for a separate call to make it deterministic afterwards.

This option requires the response format to be FAIR. If you do not set a response format, it defaults to FAIR automatically.

Code
RegexSolverClient client = RegexSolverClient.builder()
    .apiToken(System.getenv("REGEXSOLVER_API_TOKEN"))
    .build();

Term a = Term.regex("(abc|de){2}");
Term b = Term.regex("de.*");

OperationOptions options = OperationOptions.builder()
        .deterministic(true);

Term result = client.intersection(List.of(a, b), options);

List<String> page1 = client.generateStrings(result, 10, 0);
List<String> page2 = client.generateStrings(result, 10, 10);