Given a sequence s (or a finite set of sequences) I would like to know if this was generated by a regular or by a context-free (supposes these are the only options) grammar.
Of course, this is an ill-posed problem because any finite language is regular. So I am more interested in work which tried to discover context-free, non-regular structures inside a given sequence. I could think of two possible ways of doing it:
- is a smallest CF grammar "much smaller" than a smallest regular grammar? If yes, this would be a good indicator that the generative grammar should be CF
- try to find specific context-free structures (in the sense of the pumping lemma).
Any work out there I should know about?