5

$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.


1

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} = ...


1

You'll need two algorithms (definitions, actually) here: one to define a distance between answers with in questions one to define a distance between complete questionnaires It makes working with 2 easier if you choose 1 such that they are all compatible, or normalized. (For example, you can assign a distance of 1 to total disagreement like in "Nope&...


Only top voted, non community-wiki answers of a minimum length are eligible