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:

  1. 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
  2. try to find specific context-free structures (in the sense of the pumping lemma).

Any work out there I should know about?


1 Answer 1


As you already noted, a single example or any finite number of words in $L$ is not going to be the right notion. So why not look beyond? A somewhat famous paper did so in 1967 and revealed what happens when you try to learn in the limit.

An alternative interpretation of your question leads to the field of descriptive complexity theory where one looks for a minimal representation $\langle M,w\rangle$ of a string in terms of a TM $M$ and an input word $w$ to it. Asking whether a single word had been (better?) generated by a CFG or a DFA is indeed ill-posed: either one would be a special case of such a pair $\langle M,w\rangle$.

Finally, given $w\in\Sigma^*$, asking for the smallest DFA $A$ and CFG $G$ with $w\in L(A)$ and $w\in L(G)$ is going to disappoint. The simplest DFA (with just one state) and the simplest CFG (with one non-terminal) will do because the universal language $\Sigma^*$ is blatantly regular. To make this intersting you'd need some negative instances, which brings you back to reading said famous article. I recommend it.

  • $\begingroup$ Thanks for the answer. As you noted, the idea I outlined was in the direction of finding a minimal description of the sequence. Your second paragraph is correct, but the idea is that the special cases of <M,w> would have different sizes. Wrt your last paragraph, you are talking about a grammar that generates more than the positive examples. I was thinking of a grammar that generates only the given set. In the case of CFG, this is called the Smallest Grammar Problem. $\endgroup$
    – mgalle
    Commented Apr 4, 2012 at 15:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.