The design of novel antimicrobial peptides (AMPs) is an important problem given the rise of drug-resistant bacteria. However, the large size of the sequence search space, combined with the time required to experimentally test or simulate AMPs at the molecular level makes computational approaches based on sequence analysis attractive. We propose a method for designing novel AMPs based on learning from n-gram counts of classes of amino acid residues, and then using weighted finite-state machines to produce sequences that incorporate those features that are strongly associated with AMP sequences. Finite-state machines are able to generate sequences that include desired n-gram features. We use this approach to generate candidate novel AMPs, which we test using third-party prediction servers. We demonstrate that our framework is capable of producing large numbers of novel peptide sequences that share features with known antimicrobial peptides.