Mathematical modeling of behavioral sequences yields insight into the rules and mechanisms underlying sequence generation. Grooming in Drosophila melanogaster is characterized by repeated execution of distinct, stereotyped actions in variable order. Experiments demonstrate that, following stimulation by an irritant, grooming progresses gradually from an early phase dominated by anterior cleaning to a later phase with increased walking and posterior cleaning. We also observe that, at an intermediate temporal scale, there is a strong relationship between the amount of time spent performing body-directed grooming actions and leg-directed actions. We then develop a series of data-driven Markov models that isolate and identify the behavioral features governing transitions between individual grooming bouts. We identify action order as the primary driver of probabilistic, but non-random, syntax structure, as has previously been identified. Subsequent models incorporate grooming bout duration, which also contributes significantly to sequence structure. Our results show that, surprisingly, the syntactic rules underlying probabilistic grooming transitions possess action duration-dependent structure, suggesting that sensory input-independent mechanisms guide grooming behavior at short time scales. Finally, the inclusion of a simple rule that modifies grooming transition probabilities over time yields a generative model that recapitulates the key features of observed grooming sequences at several time scales. These discoveries suggest that sensory input guides action selection by modulating internally generated dynamics. Additionally, the discovery of these principles governing grooming in D. melanogaster demonstrates the utility of incorporating temporal information when characterizing the syntax of behavioral sequences.