> the system is non-deterministic means that it necessarily is probabilistic.
This is not correct. Both of the examples I gave where specifically chosen because they use non-determinism without any probabilistic framework associated.
Regex matching using non-deterministic finite automata requires absolutely zero usage of probability. You simply need to keep track of multiple paths and store whether or not any are in valid state at the end of processing the string. The list monad as non-determinism is an even more generic model of non-determinism, that again, requires nothing probabilistic in it's reasoning.
Non-deterministic things do often become probabilistic because typically you have to make a choice of paths, and that choice can have a probabilistic nature. But again, NFA regex matching is a perfect example where no "choice" is needed.
How many paths are there in that regex, say n. If n1 of those paths lead to one result, and n2 of those paths lead to another result, then you can model the probability of the first path being n1/n. There you go probability.
I do agree that there is no designed probability in that example though, but there is emergent probability.