2
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I must be dense. How can we "hard-code the answer for each of the finitely many grammars" if we, if presented with two arbitrary grammars, may not be able to determine if their intersection is non-empty in the first place? $\endgroup$ – gaazkam Jun 25 '18 at 18:00
  • $\begingroup$ This seems somehow similar to the infamous halting problem. We may have a Turing machine; and since halting problem is undecidable we may not be able to determine if this particular Turing machine ever halts. But! For each arbitrary Turing machine let us construct a language of this Turing-machine only! This is a finite language; each finite language is decidable; so it is decidable if this particular Turing machine halts; but then we have solved the halting problem in general, haven't we? $\endgroup$ – gaazkam Jun 25 '18 at 18:04
  • $\begingroup$ 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. $\endgroup$ – gaazkam Jun 25 '18 at 18:08
  • $\begingroup$ Sorry for this wall of comments; I just want to understand this problem; I fail to understand it. $\endgroup$ – gaazkam Jun 25 '18 at 18:08
  • $\begingroup$ 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. $\endgroup$ – Ted Jun 25 '18 at 18:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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