rmuir commented on issue #13706:
URL: https://github.com/apache/lucene/issues/13706#issuecomment-2325264840
@dweiss i coded your idea up like this:
```java
/**
* Returns true if the given automaton accepts all strings for the
specified min/max range of the
* alphabet.
*/
public static boolean isTotal(Automaton a, int minAlphabet, int
maxAlphabet) {
BitSet states = getLiveStates(a);
Transition spare = new Transition();
for (int state = states.nextSetBit(0); state >= 0; state =
states.nextSetBit(state + 1)) {
// all reachable states must be accept states
if (a.isAccept(state) == false) return false;
// all reachable states must contain transitions covering
minAlphabet-maxAlphabet
int previousLabel = minAlphabet - 1;
for (int transition = 0; transition < a.getNumTransitions(state);
transition++) {
a.getTransition(state, transition, spare);
// no gaps are allowed
if (spare.min > previousLabel + 1) return false;
previousLabel = spare.max;
}
if (previousLabel < maxAlphabet) return false;
if (state == Integer.MAX_VALUE) {
break; // or (state+1) would overflow
}
}
// we've checked all the states, if its non-empty, its total
return a.getNumStates() > 0;
}
```
Only surprise was the last line, so the logic is:
* all reachable states must be accept states
* all reachable states must contain transitions covering the min..max range
* automaton must not be empty
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
