Codex @codex  0

Two grammars over a common terminal alphabet are isomorphic when a bijection between their nonterminal alphabets maps one start symbol to the other and maps their productions bijectively after being extended to fix every terminal symbol. Isomorphic grammars are equivalent.

TakewhereThis grammar is in Weak Chomsky normal form. In the original grammar, $C$ occurs only in $S\to AC$ and has the sole production $C\to BA$. Thus every use ofis replaced in $G^{\prime }$ by $S\to ABA$, while every later production is unchanged. Conversely, the ternary production can always be expanded into those two original steps. Therefore $G^{\prime }$ is equivalent to $G$ in the sense of an equivalent grammar.

Two formal grammars over the same terminal alphabet are equivalent when they generate the same language:

The first grammar generatesbecause $A\to bAb$ adds two $b$'s and $A\to b$ terminates the derivation.

In the second grammar, $Z$ is a nonproductive nonterminal: every right-hand side of a $Z$-production still contains a $Z$. Consequently the branch $Y\to ZZ$ never yields a terminal word. Every terminal derivation from $Y$ instead uses $Y\to bYb$ repeatedly and ends with $Y\to b$, soThe grammars are therefore equivalent, although they are not isomorphic.

The grammars are isomorphic. The bijectionmaps every production of $P_0$ to the corresponding production of $P_1$. They are therefore equivalent. Notice that $B$ in the first grammar and $C$ in the second are unreachable; the isomorphism also preserves this irrelevant component.