6:证明和证明方法
形式语言和有限自动机,有很强的理论性, 许多的论断是以定理的形式给出的,而定理的 正确性是需要进行证明的。
形式语言和有限自动机理论中定理的证明大多使用反证法和归纳法进行。...不完全归纳法是根据一部分情况作出的推理 , 因此 , 不能作为严格的证明方法。 在形式语言与有限自动机理论中 , 大量使用数学归纳法证明某个命题。...因此,在使用数学归纳法证明某个关于非负整数n的命题P(n) 时,只需要证明(1)、(2)
两点即可。第(1)步称为归纳基础, 第(2)步称为归纳步骤。...(1) 基础:证明该集合中的最基本元素具有性质P; 而且使得该集合非空; (2) 归纳: 证明如果该集合的元素x1 ,x2 ,x3 , …,具有性质P, 则使用某种运算、函数或组
合方法对这些元素进行处理后所得的元素也具有性质...P;
(3) 由归纳法原理,集合中的所有元素也具有性质P。