The schema are inference rules and the set derivable symbols

The Art in Artificial Intelligence 15

The symbolic movement represented linguistic grammars as rewrite rules. This repre-sentation was first used by ancient Indian grammarians (especially Panini circa 350 BC) for Shastric Sanskrit [Ingerman, 1967]. The oldest known rewrite grammar is the set of natural numbers. The number 1 is the single initial sentence and the single rewrite rule appends 1 to a previously constructed number. This method of counting, where there is a one to one correspondence between a number and the number of symbols used to represent it, appeared in many societies. Some historians of the written word (e.g., [Harris, 1986]) suggest that numeracy predates literacy. In evi-dence, Harris claims that societies that did not develop counting beyond the number three did not achieve literacy by their own efforts.

Maslov [1988] uses the alternative names calculus or deductive system for rewrite

rules. A deductive system has some initial symbols {A1, …An} and some schema for deriving new symbols from the initial ones and those already constructed. In corre-spondence with theorem proving, the initial symbols are called axioms, the schema are inference rules and the set of derivable symbols, theorems. For Post, symbols expressed a finite amount of information. As such, they could be encoded by words, finite sequences of typographical letters drawn from an alphabet. Each letter itself carries no information; their only property is the distinction of one letter from an-other.

Regular expressions
Context free grammar
Context sensitive grammar Recursively enumerable set

Finite state machine
Stack machine
Linear bounded automata Turing machine