The songs of Bengalese finches (Lonchura striata var. domestica) have complex syntax and provide an opportunity to investigate how complex sequential behavior emerges via the evolutionary process. In the present study, we suggest that a simple mechanism, i.e., many-to-one mapping from internal states onto syllables, may underlie the emergence of apparent complex syllable sequences that have higher-order history dependencies. We analyzed the songs of Bengalese finches and of their wild ancestor, the white-rumped munia (Lonchura striata), whose songs are more stereotypical and simpler compared to those of Bengalese finches. The many-to-one mapping mechanism sufficiently accounted for the differences in the complexity of song syllable sequences of these two strains.