  We show that the Parikh image of the language of an NFA with n states over an
alphabet of size k can be described as a finite union of linear sets with at
most k generators and total size 2^{O(k^2 log n)}, i.e., polynomial for all
fixed k >= 1. Previously, it was not known whether the number of generators
could be made independent of n, and best upper bounds on the total size were
exponential in n. Furthermore, we give an algorithm for performing such a
translation in time 2^{O(k^2 log(kn))}. Our proof exploits a previously unknown
connection to the theory of convex sets, and establishes a normal form theorem
for semilinear sets, which is of independent interests. To complement these
results, we show that our upper bounds are tight and that the results cannot be
extended to context-free languages. We give four applications: (1) a new
polynomial fragment of integer programming, (2) precise complexity of
membership for Parikh images of NFAs, (3) an answer to an open question about
polynomial PAC-learnability of semilinear sets, and (4) an optimal algorithm
for LTL model checking over discrete-timed reversal-bounded counter systems.
