A total of 78 adult participants were asked to read a sample of strings generated by a finite state grammar and, immediately after reading each string, to mark the natural segmentation positions with a slash bar. They repeated the same task after a phase of familiarization with the material, which consisted, depending on the group involved, of learning items by rote, performing a shortterm matching task, or searching for the rules of the grammar. Participants formed the same number of cognitive units before and after the training phase, thus indicating that they did not tend to form increasingly large units. However, the number of different units reliably decreased, whatever the task that participants had performed during familiarization. This result indicates that segmentation was increasingly consistent with the structure of the grammar. A theoretical account of this phenomenon, based on ubiquitous principles of associative memory and learning, is proposed. This account is supported by the ability of a computer model implementing those principles, PARSER, to reproduce the observed pattern of results. The implications of this study for developmental theories aimed at accounting for how children become able to parse sensory input into physically and linguistically relevant units are discussed.