In our course: Automata and Computation there is a definition about Context-Free Grammars which states:

"Two CFG's $CFG_{1}$ and $CFG_{2}$ are equivalent if $L_{CFG_{1}} = L_{CFG_{2}}$ where $L_{CFG_{i}}$ is the language that is derived by $CFG_{i}$".

Below the definition, it is stated that this defines an equivalence relation of the CFG's, but I don't see how I could prove this. I know that I should prove the 3 properties of an equivalence relation being:

-Reflexive -Symmetric -Transitive

But how can I do this for the particular problem?

  • 4
    $\begingroup$ Did you ever prove that a relation is an equivalence relation? If you didn't, check how it's proved in other cases (see some examples of equivalence relations here), this one is the same. $\endgroup$
    – Dmitry
    Nov 22 '21 at 16:52
  • $\begingroup$ Yes I did, but I don't see how I can translate proving that a relation is an equivalence relation to proving that this is also the case for CFG $\endgroup$ Nov 22 '21 at 17:33

Let $\mathcal{G}$ be the set of all context-free grammars and let $\rho \subseteq \mathcal{G}^2$ denote the binary relation "being equivalent to".

Let $G$ be a CFG grammar. Clearly it holds that $G \rho G$ since $L_G=L_G$. Therefore $\rho$ is reflexive.

Let $G$ and $G'$ be CFG grammars such that $G \rho G'$. By definition of $\rho$ we have $L_{G} = L_{G'}$ and since set-equality is symmetric we also have $L_{G'} = L_{G}$. This shows that $G' \rho G$ and hence $\rho$ is symmetric.

Let $G$, $G'$ and $G''$ be CFG grammars such that $G \rho G'$ and $G' \rho G''$. By definition of $\rho$, we have $L_G = L_{G'}$ and $L_{G'} = L_{G''}$ and by transitivity of set-equality we have $L_G = L_{G''}$ showing that $G \rho G''$ and that $\rho$ is transitive.

  • $\begingroup$ So basically if something like this is asked, it's best to define a relation like "being equivalent to" and proving that that is an equivalence relation? $\endgroup$ Nov 22 '21 at 18:51
  • $\begingroup$ The relation was already defined in the question. I just named it with a symbol ($\rho$) for brevity. $\endgroup$
    – Steven
    Nov 22 '21 at 19:02
  • $\begingroup$ Oh now I see where I missed. Looks like I just didn't pay enough attention to the question. $\endgroup$ Nov 22 '21 at 19:18
  • 1
    $\begingroup$ @Nathaniel thanks for the edit! $\endgroup$
    – Steven
    Nov 22 '21 at 19:56
  • $\begingroup$ You're welcome! $\endgroup$
    – Nathaniel
    Nov 22 '21 at 20:06

$G_1$ and $G_2$ are equivalent if and only if $L_{G_1} = L_{G_2}$.

Since the relation $=$ is an equivalence relation over languages, so is the equivalence between grammars.


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.