To learn a new language, it is necessary for the learner to succeed in segmenting the continuous stream of sounds into significant units. Previous behavioral studies have shown that it is possible to segment a language or musical stream based only on probabilities of occurrence between adjacent syllables/tones. Here we used a sung language and tested participants' learning of both linguistic and musical structures while recording electroencephalography. Although behavioral results showed learning of the linguistic structure only, event-related potential results for both dimensions showed a negative component sensitive to the degree of familiarity of items. We discuss this component as an index of lexical search, also pointing to the greater sensitivity of the event-related potentials compared to the behavioral responses.