研究一个重写问题的产生式系统，其初始数据库为（C，B，
Z），产生式规则的依据是如下的重写规则： R1：C→（D，L） R2：C→（B，M） R3：B→（M，M） R4：Z→（B，B，M） 结束条件是生成出只包含M组成的数据库，即（M，…，M）。
用图搜索方式求解这个问题时，搜索得到的部分状态空间图。 图中只给出两条达到目标的路径和一条失败的路径。实际搜索时有可能 去探索更多的路径，往往导致效率降低。
重写问题的与或树
（3）若对D应用某一规则序列之后得到一个数据库D′（设
简例：给定一个整数集合{a，b，c}，可通过把集合中任意
一对元素的乘积作为新元素添加到集合中的办法来扩大该整 数集，要求通过若干次操作后能生成出所需的整数集合来。
其综合数据库就可用集合表示，则问题的初始状态为{a，b，
c}，设目标条件为具有a，b，c，ab，bc，ca这六个元素组 成的集合，初始状态可应用的规则集合为：
（1）可应用于D的规则集合，对用了其中任意一条规则之后 所生成的任何数据库，这个规则集合还适用； （2）满足目标条件的某个数据库D，当应用任何一个可应用 于数据库D的规则之后所生成的任何数据库，仍然满足目标 条件； 有一对应于D→D′的一条解路），则当改变D的可应用规则 集合中的规则次序后，仍然可求得解，即求得D′与使用满 足D的可应用规则集合中的规则次序无关。
八数码游戏
（1）综合数据库：通常用来表示综合数据库的数据结构有符号串、向量、 集合、数组、树、表格、文件等。该问题的综合数据库可以如下形式表 示：(Sij)，其中1≤i、j≤3， Sij ∈{0,1,…,8}，且互不相等。 （2）规则集合：移动一块牌（即走一步）就使状态发生转变。改变状态有4 种走法：空格左移、空格上移、空格右移、空格下移。可用4条产生式规 则来模拟
可交换的产生式系统
可交换性是指几条规则可以任意交换次序而不影响求解。但
要注意并不是所使用的整个规则序列可以重新排列，只有那 些最初可应用于初始数据库的规则才可交换，而对于生成的 数据库所添加的其他可应用规则，则不能随意交换。

一般来说，当一个产生式系统对任何一个数据库D都具 有如下性质时，这个产生式系统是可交换的：
整数集合生成问题的部分状态空间图
如果一个产生式系统可以分解为几个子问题，当子问题得以
求解时，则原始问题被求解。这样的产生式系统称为可分解 的产生式系统。
如果原始问题可以被划分为几个独立的子问题来求解，则可
以提高问题求解的效率。但在很多情况下，子问题之间并不 是完全独立的，它们之间会有某些方面的联系，这样的可分 解产生式系统可以表示为一个与或树（图）。
产生式系统的控制策略
控制策略可划分为两大类：
（1）不可撤回方式：爬山法

八数码游戏例: 用"不在位"将牌个数并取其 负值作为状态描述的函数－ W（n）（"不在位"将牌个 数是指当前状态与目标状态 对应位置逐一比较后有差异 的将牌总个数，用W本过程描述如下： 过程 SPLIT （1）DATA:＝初始数据库 （2）{Di}:＝DATA的分解式；每个Di元素都看成单独的数据 库 （3）Until {Di}的所有元素都满足结束条件之前，do： （4）begin （5）从{Di}中选一个不满足结束条件的D* （6）从{Di}中删去D* （7）在规则集中选择一条可应用于D*的规则R （8）D:＝R应用于D*的结果 （9） {di}:＝D的分解式 （10）在{Di}上添加di （11）end
（2）回溯方式：在问题求 解过程中，有时会发现 应用一条不合适的规则 会阻挠或拖延达到目标 的过程。在这种情况下， 需要有这样的控制策略： 先试一试某一条规则， 如果以后发现这条规则 不合适，则允许退回去， 另选一条规则来试。
（3）图搜索方式：如果把问题求解过程用图或树的这种结构来描述，即图 中的每一个节点代表问题的状态，节点间的弧代表应用的规则，那么问 题的求解空间就可由隐含图来描述。图搜索方式就是用某种策略选择应 用规则，并把状态变化过程用图结构记录下来，直到得出解为止。