# Is any context-free grammar in Chomsky form with at most 2017 rules necessarily finite?

A task from one of the former tests:

Is there any algorithm, which for all pairs of context-free grammars over $\lbrace a,b,c\rbrace$ in Chomsky form $G_1,G_2$ with at most $2017$ rules correctly answers whether $\operatorname{L}(G_1)\cap\operatorname{L}(G_2)=\emptyset$?

This question is from a single choice test, only a Yes / No answer is expected, no proof is needed. Well, my intuition very strongly leans towards the No answer, so strongly that I would check it even though I can't prove it.

Then I looked at the solution. Apparently, the answer is Yes. I'm perplexed. I'm even more perplexed by the short explanation the solution sheet attaches:

Each finite language is decidable.

Wait. Why do $\operatorname{L}(G_1),\operatorname{L}(G_2)$ have to be finite?

I believe I have a simple counter-example for this? Here is a context-free grammar over $\lbrace a,b,c\rbrace$ in Chomsky form with at most $2017$ rules that is infinite:

$$S\longrightarrow AS\\ S\longrightarrow b\\ A\longrightarrow a$$

It simply represents the language $a^\star b$.

I fail to understand the solution to this task - could you kindly explain it to me?

The "language" mentioned in the explanation is not $L(G_1)$ or $L(G_2)$.

The "language" here refers to the input to the algorithm (i.e., the language being recognized by the algorithm). The language in question is the set of context free grammars over $\{a,b,c\}$ in Chomsky form with at most 2017 rules. There are only finitely many such grammars (since there are at most 2017 rules, and in Chomsky form, the right side of each rule has at most 2 symbols), so we just need to hard-code the answer for each of the finitely many grammars.

If we replace 2017 by a general $n$, then for each n, such an algorithm $T_n$ exists. However, there is no "algorithm to construct the algorithm", i.e., no algorithm that given an $n$, outputs $T_n$ for each $n$. That's why this doesn't contradict the result about undecidability of the intersection of two CFG's in general.
• Finally, by your argumentation, for any natural $n$ it is decidable if intersection of two CFGs in Chomsky form with at most $n$ rules is non-empty, since for any natural $n$ the language of these grammars is finite. But this, again, implies that we have solved CFG intersection emptiness problem in general: if presented with two arbitrary CFGs, first we convert them to Chomsky form, then we take $n:=max(|G_1|,|G_2|)$, then we say that for this particular $n$ the problem is decidable. Jun 25, 2018 at 18:08
• Regarding your comment on the CFG intersection problem: to solve the CFG intersection emptiness problem, you have to give a single algorithm for all pairs of CFG's. You've given a different algorithm for each $n$. Similarly for your comment about the halting problem: You've given a different algorithm for each Turing machine, but you need to give a single algorithm for all Turing machines.