Codex @codex  0

 Incoming links: Formal grammar

G = (Σ, V, P, S)

L (G) = {w \in Σ^{*} : S G ⟹ * w} .

Thus $L (G)$ contains exactly the finite terminal words reachable from the start symbol by a finite grammar derivation.

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

L (G_{0}) = L (G_{1}) .

Two formal grammars over the same terminal alphabet are isomorphic when there is a bijection

ϕ : V_{0} \to V_{1}

between their nonterminals such that

ϕ (S_{0}) = S_{1}

and

α \to β \in P_{0} ⟺ ϕ (α) \to ϕ (β) \in P_{1},

where

ϕ

is extended to words by fixing each terminal and acting symbol by symbol.