Method for measuring the 'similarity' between FSA grammars? I'm working with a pattern matching algorithm that generates an acyclic finite state automaton that accepts a given text string and all its substrings. The FSA algorithm is being run on a symbolic representation of a music stream (e.g., MIDI data). The music stream has been preprocessed to divide each song into unlabeled 'segments'. An FSA is generated for each segment in each song: if I have $n$ songs, each divided into $y$ segments, I will have $n \cdot y$ separate FSAs. 

I would like to compare each segment's FSA with the other FSAs in my corpus. The ultimate goal would be to do clustering within a similarity space and come up with 'classes' of segments according to how similar their construction metrics are. Thus, of particular interest are the grammars that each FSA defines (corresponding roughly certain components of the musical content in the segment). Are there techniques that might be good for comparing something like this? KL-divergence comes to mind (e.g., using it compare the distribution over strings associated with a given FSA), although there may be better/more efficient techniques?  

Also, apologies if this question is either (1) trivially easy or (2) indicative of some deeper misunderstanding or (3) answered elsewhere. I'm a real nub, folks!
you might have more luck from another angle &amp; looking into research into music piece similarity, there are researchers studying that, and while your approach can work, there are other approaches. there are large databases that look at many elements/ criteria such as lyrics, genre etc. eg Music genome project.

sometimes when theres a wide variety of algorithms a survey can help. here are two surveys on graph matching.


Matching Structure and Semantics: A Survey on Graph-Based Pattern Matching
Brian Gallagher
Graph Similarity and Matching / Zager