# 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'll need to tell us what you mean by "similar". You have to select the metric; there is no one right metric that is right for all purposes. Without more information, we can't tell you what metric to use. I suggest editing the question to explain why you want to measure similarity, what you will do with the results of the similarity metric, and what research you have done. You might start by looking at measures of similarities between the underlying strings, rather than measuring the similarities of the FSAs derived from those strings. Edit distance comes to mind. – D.W. Sep 10 '14 at 4:46
• There are many string metrics; which works for you depends. (Note: some of the string "metrics" listed in that article are not actually metrics in the mathematical sense.) – Raphael Sep 10 '14 at 8:41
• String metrics are good, but not quite what I'm after. Instead of comparing specific strings to one another, I'd like to compare the system of rules (the formal grammars/FSAs) that could have produced those strings. I recognize that there are infinitely many grammars that can produce any specific string, so I'm constraining my search to a grammar (FSA) constructed using a particular set of rules. I imagine there might be cases where two individual strings are formally similar according to a given string metric, but the grammars required to produce them are quite different – flip Sep 10 '14 at 20:28
• From the statement of the problem, each FSA is accepting one string and all its substrings. Fundamentally, this FSA is characterized by the longest string it accepts. Its whole structure derives from it. Hence there is little point in comparing the FSA rather than directly comparing the strings they are constructed from. It may be that your FSA construction technique emphasizes some features, which you consider important. Then we need to know what they may look like so as to understand what matters. It comes back to: what is similar, what metric. As it is, this question makes no sense. – babou Aug 11 '15 at 8:56