  We investigate a subclass of languages recognized by vector addition systems,
namely languages of nondeterministic Parikh automata. While the regularity
problem (is the language of a given automaton regular?) is undecidable for this
model, we show surprising decidability of the regular separability problem:
given two Parikh automata, is there a regular language that contains one of
them and is disjoint from the other?
