3
$\begingroup$

Is there a way to show that for all finite sets $S$ of context free grammars, there exists a Turing Machine $M$ such that for all grammars $G_1, G_2 \in S$, we have that $M(G1,G2)$ terminates and answer yes if and only if $L(G_1)=L(G_2)$? Is that even true?

I know that this problem is in general undecidable, but I also know that a finite set is in general decidable. I just can't figure out how to determine the answer for this problem.

Improve this question
$\endgroup$
7
  • 1
    $\begingroup$ When you say for all sets S of context free grammars, do you mean for all finite sets S of context free grammars? If so, then there does exist a Turing machine for $M_S$ which decides where $L(G_1) = L(G_2)$ for $G_1, G_2 \in S$. The reason? There are finitely many comparisons (in fact, $|S|^2$ of them) and the Turing machine may have the correct result hard-coded for each case. Since any two grammars can be compared via equality, the function is computable, even if we (in general) have no algorithmic way to determine the values to hard-code into the TM. $\endgroup$
    – Patrick87
    Feb 11, 2014 at 21:18
  • $\begingroup$ @Patrick87 Even assuming that's what he meant, that still only proves that $\forall$ finite sets of grammars, $\exists$ a TM that decides language equality. It doesn't show that $\exists$ TM which $\forall$ finite sets of grammars decides equality. $\endgroup$
    – G. Bach
    Feb 11, 2014 at 21:52
  • $\begingroup$ Yes sorry, i meant for all FINITE sets S ... $\endgroup$
    – user222
    Feb 11, 2014 at 21:59
  • $\begingroup$ What i don't get is the reason behind the "may have the correct result hard-coded for each case". I mean, I give you a set S with a finite number of CFG Grammars, how can you even know that two of them generates the same language? Where does that piece of knowledge come from? The problem says that for all S exists M, what does make it true in general? Sorry if it sounds stupid but I really don't get it. $\endgroup$
    – user222
    Feb 11, 2014 at 22:14
  • 1
    $\begingroup$ @G.Bach Yes, I assume he meant the former, since otherwise my argument doesn't really make any sense. Looking at his question again, it does appear he's asking it so that my comment applies: for all finite sets S, does there exist a TM? Not: does there exist a TM, such that for all finite sets S, ... $\endgroup$
    – Patrick87
    Feb 11, 2014 at 22:14

2 Answers 2

Reset to default
8
$\begingroup$

A problem is decidable if there is a TM which decides instances of the problem.

Given two arbitrary CFGs $G_1$ and $G_2$, we know this for certain: either $L(G_1) = L(G_2)$, or $L(G_1) \neq L(G_2)$. Consider the first case: a TM that accepts on the input $(G_1, G_2)$ correctly decides this problem. Consider the second case: a TM that rejects on the input $(G_1, G_2)$ would be correct in that case.

Now, consider a finite set of grammars $\{G_1, G_2, ..., G_n\}$. For any two grammars $G_i$ and $G_j$ in this set, we know that either $L(G_i) = L(G_j)$ or $L(G_i) \neq L(G_j)$.

Consider the following TMs:

TM #1:

if input is (G_1, G_1) then accept
if input is (G_1, G_2) then accept
...
if input is (G_n, G_n) then accept

TM #2:

if input is (G_1, G_1) then accept
if input is (G_1, G_2) then accept
...
if input is (G_n, G_n) then reject

...

TM #N

if input is (G_1, G_1) then reject
if input is (G_1, G_2) then reject
...
if input is (G_n, G_n) then reject

Each TM can either accept or reject for each of the $n^2$ (ordered) inputs; so there are $N = 2^{n^2}$ different TMs (as many as binary strings of length $n^2$).

One of these TMs is guaranteed to correctly decide your problem. I can't tell you which one, but one of these gives all the correct answers. Since there is a TM for your problem, it's decidable.

Improve this answer
$\endgroup$
2
  • $\begingroup$ My hero. Thank you very much, it's all clear now! $\endgroup$
    – user222
    Feb 11, 2014 at 22:35
  • $\begingroup$ The existential argument is also found in other contexts. $\endgroup$
    – Raphael ♦
    Feb 12, 2014 at 17:26
-1
$\begingroup$

It is undecidable if two grammars generate the same language (see here), so this (more general) question is undecidable too.

Improve this answer
$\endgroup$
1
  • 2
    $\begingroup$ Actually the undecidable problem is a generalization of this question, since the undecidable problem is "given two grammars, do they produce the same language?", which translates to "$\exists$ a TM $M$ such that $\forall G_1, G_2$, $M$ decides whether $L(G_1) = L(G_2)$?" In the question of user222, the quantifiers are switched, so there may be many TMs, each only deciding equality of a specific finite subset of all grammars. $\endgroup$
    – G. Bach
    Feb 11, 2014 at 22:56

Your Answer

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

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