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