设
w1?s1s2s3?sn,
?w2?t1t2t3?tk属于A*, 都是集合A的单
词。记单词w1w2?s1s2s3?snt1t2t3?tk为w1, w2的连接catenation，
w1?w2?A*。
设?是空串，
w?A*，则??w?w???w。
A的正则表示
a regular expression over A.
设A是一个字符集，由如下产生规则生成的字符串叫做A的正则表示, 不引起歧义时简称正则表示，省略A：
?是正则表示。
Re2. 如果x?A,则x是正则表示。
Re1. 空串
Re3. 如果α，β是正则表示，则αβ，即α?β，是正则表示。 Re4. 如果α，β是正则表示，则(α∨β)是正则表示。 Re5. 如果α是正则表示，则(α)*是正则表示。
Re1, Re2 是初始正则表示，其余是递归定义。α首末有括号时，(α)*简写成α*，即去掉多重括号。
例 设A={0,1}，则 0*(0∨1)*， 00*(0∨1)*1 ，(01)*(01∨1*) 都是A的正则表示。
正则集
regular subsets or just regular sets
设A是一个字符集，A的每个正则表示对应A*的一个子集，这些集合叫做A*的正则集合，简称正则集合。正则集合的生成规则如下： 1． 正则表示2． 如果
?对应的集合是{?}。
x?A，那么正则表示x对应的集合是{x}.
?3． 如果α，β是正则表示，α对应的正则集合是M，β对应的正则集合是
N, 则αβ对应的正则集合是 M?N={st|s?M?t?N}.
4． 如果α，β是正则表示，α对应的正则集合是M，β对应的正则集合是N, 则(α∨β)对应的正则集合是。
5． 如果α是正则表示，α对应的正则集合是M， 则(α)*对应的正则集合是
M*。
M?N 例 设A={a,b,c}, 正则表示a*对应的集合为
{a|n?N}?A*，
n其中an=aa……a, 即n个a组成的字符串。 正则表示
a(b?c)对应的正则集合是{ab,ac}?A*.
1.4整除Divide 1.4.1整除
定理1 （带余除法）对任意两个整数n, m, n>0,存在整数q, r, 0?r q叫做商quotient, r叫做余数reminder. 如果整数m是n的倍数, n>0, 即存在整数q, 使m?qn，带余除法 中r=0, 就称n整除m, 记作n|m.否则就说n不整除m。 定理2. 设a, b, c是整数， (a) (b) (c) (d) a|b, a|c ? a|(b+c) a|b, a|c, b>c a|b或 a|c a|b, b|c ? a|(b－c) ? a|bc ? a|c 1.4.2素数 prime 一个正整数p>1, 只被p和1 整除，就称p是素数。 验证一个整数N>1,是否素数的算法： 1． 如果N=2, N是素数，否则继续， 2． 如果2|N，N不是素数，否则继续， 3． 4． 求最大整数K，k看是否有奇数D, 否则N是素数。 ?N, 继续， , 如果D|N, 则N不是素数， 1?D?K 4最多执行k-2次，最多一共执行k-2+3=k+1= N?1步。 因数分解factoring 定理3. （唯一分解定理）任意一个正整数n, 都可以唯一地分解为 k1k2ksn?pp?p素数因数的连乘积：其中p1?p2???ps 是12s， 整除n的所有互不相同的素数因数，正整数ki，1?素数因子pi 在n中出现的次数。 例 9=32， 24=23?3，30=2?3?5。 i?s分别是 1.4.3最大公约数 Greatest Common Divisor 公约数Common Divisor ?a,b,k?Z如果, k|a, k|b,就称k是a,b的公因数，或公因子。 最大的一个公因数d就叫最大公因数，记作d=GCD(a,b) 定理4. (a)设d=GCD(a,b)则存在整数s,t使d=sa+tb.(s,t不是必须为正) (b)如果c是a,b的公因数，则c|d. proof. Let x be the smallest positive integer that can be a common divisor of a and b. Since c|a, and c|b, if follows from Theorem 2 that c|x, so c?x. If we can show that x is a common divisor of a and b, it will then be the greatest common divisor of a and b and both parts of the theorem will have been proved. By Theorem 1, a=qx+r with 0?r The fact x is the smallest positive integer that can be written as a sum of multiples of a and b, gives r=0. Thus x|a. In the same way we can show that x|b, and the proof is complete. Corollory d=GCD(a, b) if and only if (a) d|a and d|b. (b) whenever c|a and c|b, then c|d. Theorem 5. If a,b∈Z+ (a) GCD(a, b)=GCD(a,a±b)=GCD(a, a±qb) (b) If 0 用Euclid辗转相除法可以得到GCD(a,b),a?b>0: a=q1b+r1, 0?r1 rn-2=qnrn-1+rn, 0?rn 余数越来越小最后等于0。 GCD(a,b)=rn, 这是因为 GCD(a,b)=GCD(b,r1)=GCD(r1,r2)=……=GCD(rn-1,rn)=rn. 定义 如果GCD(a, b)=1, 就说a, b 互素。 Proposition (a) a, b互素当且仅当存在整数s和t使sa+tb=1. (b) a/GCD(a,b), b/GCD(a,b) 互素 1.4.4最小公倍数Least Common Multiple 设 a, b, k∈Z+，a|k, b|k, 称k是a,b的公倍数。公倍数中最小的一个c叫最小公倍数,记作c=LCM(a,b)。
相关推荐：
loading