Grammar

is a grammar if is a RWS. is the start symbol.

Assume and , is the set of alphabet letters is the set of variables

is the set of words is a formal language. Derivable Strings Variable-based Grammar Set of all Grammars

Definition

Two grammars are equivalent if they generate the same Formal Language.

Proposition

Isomorphic grammars are equivalent.