1.3.1　形式语言与注册机

一个有穷非空的字符集合V称为字母表。字母表中的元素称为字符。V中一个长度有限的序列称为一个字符串。不含任何字符的空串记为λ。来自V的所有字符串记为V*；来自V中的非空字符串集合V*－λ，记为V＋。对于一个字符串x，其中包含的字符总数称为x的长度，记为｜x｜。对于任意两个字符串x和w，字符串x和w所组成的字符串称为它们的连接，记为xw。如果V＝｛a｝（V为单字母集合），则｛a｝*、｛a｝＋分别简记为a*、a＋。

字母表V上的一个多重集M是映射M：V→N，N表示自然数集合，N∈｛1，2，…｝。若a∈V，M（a）表示a在该多重集中的重数。对于有穷集合V，V＝｛a1，…，an｝，多重集为｛（a1，M（a1））…，（an，M（an））｝。多重集M的支撑集是集合supp（M）＝｛a∈V|M（a）＞0｝。若支撑集是空集，该多重集记为Ø。对于有穷支撑集的多重集M，｛（a1，M（a1））…，（an，M（an））｝可以用串表示为

对于P系统的计算能力，一般的研究方法是模拟注册机或者矩阵文法来对其计算通用性进行证明。本书采用模拟注册机的方法。从数学上已经证明，只要构造一个系统模拟了注册机的计算过程，那么就可以证明该系统是计算通用的。注册机是一个五元组M＝（m，H，l0，lh，I），其中，m表示注册器的个数，H表示指令标签集合，l0表示初始指令（是加法指令），lh表示注册机终止指令，I表示指令集合。注册机中指令的定义如下。

（1）加法指令li：（ADD（r），lj，lk）。将存储在注册器r中的数加1，然后非确定选择指令lj或者lk在下一步执行。

（2）减法指令li：（SUB（r），lj，lk）。首先判断注册器r中的数是否为0。若不为0，将该数字减1，下一步执行指令lj；否则，下一步执行指令lk。

（3）终止指令lh：HALT。终止整个计算，这时注册器1中的数字就是计算结果。

在产生模式下，最初存储在注册器中的数字都为0，然后，第一步执行指令l0（是加法指令），其后每一步执行一条指令（加法、减法或者终止指令）。通过执行相关指令，可以改变注册器中的内容。最后，通过执行终止指令，从而使整个计算停止。这时，我们把存储在注册器1中的数字称为注册机产生的数字。根据以上计算方式获得所有数值构成的集合，记为N（M）。已经证明，注册机在产生模式下可以刻画递归可枚举语言的长度集合（即NRE）。