在一个系统中,根据有限的重写规则,形式语言的词语(表达式)可以被转换,这样的系统被称为归约系统。虽然归约系统也称为字符串重写系统或项重写系统,但术语“归约系统”更通用。
Lambda 演算是一个归约系统的例子,其中lambda 转换规则构成了其重写规则。
如果归约系统的任何重写规则都不适用于表达式 ,则称
对于该归约系统处于范式。
如果表达式对 中的
和
都可以通过零个或多个归约步骤(即,重写规则的应用)归约到相同的表达式,则称该表达式对是可连接的。
如果 在一步中归约到
,则表示为
。如果
在零个或多个步骤中归约到
,则表示为
。如果存在一个序列
使得
,
,并且对于每一对
,要么
要么
,则使用符号
。