Rewrite Rule

Let be a finite set of symbols.
Take a nonempty string , and a string , then is called a rewrite rule (or production rule)
The set of rewrite rules is (this is countable)

Given a set of terminal symbols and variables with we define the following:

Noncontracting

A production rule is called noncontracting if

Context-free

A production rule is called context free if and

Regular

Production rules and are called regular if and