This work introduces a new kind of affine semigroups called $P$-semigroups. Within the framework of $\mathcal C$-semigroups, we define a finite-state automaton associated to them. Moreover, this automaton determines whether a $\mathcal C$-semigroup is a $P$-semigroup, which represents a bridge between affine semigroups and Discrete Mathematics. Furthermore, some algorithms for computing all the $P$-semigroups with a fixed Frobenius element, genus, or multiplicity are provided.