2
$\begingroup$

If two CFG's differ only in what names they use for their non-terminals, are they different?

For example, are these CFG's different:
$$\begin{align*} S &\to A \\ A &\to a \end{align*}$$ and $$\begin{align*} S &\to B \\ B &\to a \end{align*}$$

$\endgroup$
  • $\begingroup$ Depends on your definition of "different", obviously. $\endgroup$ – Raphael Apr 10 at 5:57
3
$\begingroup$

Two grammars $G_1 = \langle \Sigma, V_1, S_1, P_1 \rangle$ and $G_2 = \langle \Sigma, V_2, S_2, P_2 \rangle$ are

  • weakly equivalent if $L(G_1) = L_(G_2)$

  • strongly equivalent if $L(G_1) = L_(G_2)$ and for every string $w$ in the language, the minimal left-most derivations of $w$ in $G_1$ and the minimal left-most derivations of $w$ in $G_2$ are exactly the same in number, and can be put in one-to-one corresponce (note that the number of derivation trees must be the same in number if the grammars are ambiguous, i.e. they must be ambiguous "in the same way")

Example:

$G_1 = S \to A; A \to 1B; A\to 1; B\to 0A$; we have $L(G_1) = \{ (10)^*1 \}$

$G_2 = S \to B; B \to A1; B\to 1; A\to B0$; we have $L(G_2) = \{ 1(01)^* \}$

  • isomorphic if there is a bijection $\phi : V_1 \to V_2$ such that $\phi(S_1) = S_2$ and $\phi(P_1) = P_2$ (after extending $\phi$ to productions and set of productions in the natural way).

Note that weakly equivalence is undecidable, while strongly equivalence (and ismorphism) are decidable.

As a final remark I think that - in most formal language contexts - it would be fine to say that the grammars in your question are the same grammar :-)

$\endgroup$
1
$\begingroup$

Different, but equivalent (in a certain sense).

Usually a CFG is defined as a tuple $(N, T, S, P)$ where $N$ and $T$ are the sets of non-terminals, $S \in N$, and $P$ is the set of productions. Using this definition, the two grammars would be necessarily different since you have different sets of non-terminals (and different productions).

Nevertheless, you could also say the two CFGs are equivalent in the sense that the two are equal up to renaming the non-terminals. This is a stronger equivalence than, for instance, simply generating the same language.

As an aside, note an equivalence based on renaming the terminal symbols (or even both terminals and non-terminals) is also conceivable.

$\endgroup$
1
$\begingroup$

Formally, the two grammars are different. On the other hand, they obviously generate the same language and thus they are equivalent.

But beyond equivalence they are also structurally equal. This equality up to renaming symbols is probably best captured by the concept of isomorphism.

$\endgroup$

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.