[FOM] Formation Rules

John McCarthy jmc at steam.Stanford.EDU
Fri Oct 20 15:38:31 EDT 2006

I think it is too limiting to regard formal languages as sets of
strings.  It is better consider them as algebraic structures, of which
strings are an example.  I proposed abstract syntax in my 1962 IFIPS
Congress paper "Towards a mathematical science of computation".
Interpretations, inference rules, and compilation rules are more
readily defined using appropriate abstract syntaxes.  Making formal
languages algebraic structures permits imposing conditions like such
as, for example, And(p,q) = And(q,p) if one wants to make
commutativity of And part of the language definition.

More information about the FOM mailing list