<p>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 <a href="http://en.wikipedia.org/wiki/Language_identification_in_the_limit">learn in the limit</a>.</p>

<p>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$.</p>

<p>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.</p>

CC BY-SA 3.0
2012-04-04T15:11:24.523Z
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.
mgalle
CC BY-SA 3.0
2012-04-04T12:49:55.597Z
2012-04-04T12:49:55.597Z
Kai
<p>Given a sequence <em>s</em> (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.</p>

<p>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:</p>

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

<p>Any work out there I should know about?</p>

CC BY-SA 3.0
2012-04-04T12:07:45.820Z
A related question for regular languages (finding a deterministic finite automaton of minimum number of states given positive and negative examples): [Is finding the minimum regular expression an NP-complete problem?](http://cstheory.stackexchange.com/questions/1854/is-finding-the-minimum-regular-expression-an-np-complete-problem)  Also, your question might be related to learning theory.
Tsuyoshi Ito
<fl.formal-languages><grammars><context-free>
Decide if a given sequence is regular or context-free
mgalle
# Decide if a given sequence is regular or context-free

(Asked by: username_0 on 2012-04-04)

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?

**Tags:** fl.formal-languages, grammars, context-free

> **Comments:**
> **username_1**: A related question for regular languages (finding a deterministic finite automaton of minimum number of states given positive and negative examples): [Is finding the minimum regular expression an NP-complete problem?](http://cstheory.stackexchange.com/questions/1854/is-finding-the-minimum-regular-expression-an-np-complete-problem)  Also, your question might be related to learning theory.  

---

## 1 answers

### Answer by username_2 on 2012-04-04. Score: 5

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](http://en.wikipedia.org/wiki/Language_identification_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.

> **Comments:**
> **username_0**: 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.  

---

