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.
Clarification based on comments:
It is true that there is no algorithm in general to determine whether the intersection of two CFG's is empty. However, we know there is an answer for each particular pair of CFG's and therefore if we have only finitely many pairs to decide, there definitely exists an algorithm that gives the right answer for those finitely many pairs.
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.