形式化说明技术

《形式化说明技术》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第4章形式化说明技术4.1概述4.2有穷状态机4.3Petri网4.4Z语言4.5小结习题按照形式化的程度，可以把软件工程使用的方法划分成非形式化、半形式化和形式化3类。用自然语言描述需求规格说明，是典型的非形式化方法。用数据流图或实体-联系图建立模型，是典型的半形式化方法。所谓形式化方法，是描述系统性质的基于数学的技术，也就是说，如果一种方法有坚实的数学基础，那么它就是形式化的。用自然语言书写的系统规格说明书，可能存在矛盾、二义性、含糊性、不完整性及抽象层次混乱等问题。所谓矛盾是指一组相互冲突的陈述。二义性是指读者可以用不同方式理解的陈述。4.1概述4.1.1非形

2、式化方法的缺点系统规格说明书是很庞大的文档，因此，几乎不可避免地会出现含糊性。实际上，这样笼统的陈述并没有给出任何有用的信息。不完整性可能是在系统规格说明中最常遇到的问题之一。抽象层次混乱是指在非常抽象的陈述中混进了一些关于细节的低层次陈述。这样的规格说明书使得读者很难了解系统的整体功能结构。数学最有用的一个性质是，它能够简洁准确地描述物理现象、对象或动作的结果，因此是理想的建模工具。数学特别适合于表示状态，也就是表示“做什么”。4.1.2形式化方法的优点在软件开发过程中使用数学的另一个优点是，可以在不同的软件工程活动之间平滑地过渡。不仅功能规格说明，而且系统设计也

3、可以用数学表达，当然，程序代码也是一种数学符号(虽然是一种相当繁琐、冗长的数学符号)。数学作为软件开发工具的最后一个优点是，它提供了高层确认的手段。可以使用数学方法证明，设计符合规格说明，程序代码正确地实现了设计结果。(1)应该选用适当的表示方法。(2)应该形式化，但不要过分形式化。(3)应该估算成本。(4)应该有形式化方法顾问随时提供咨询。(5)不应该放弃传统的开发方法。(6)应该建立详尽的文档。(7)不应该放弃质量标准。(8)不应该盲目依赖形式化方法。(9)应该测试、测试再测试。(10)应该重用。4.1.3应用形式化方法的准则下面通过一个简单例子介绍有穷状态机的

4、基本概念。一个保险箱上装了一个复合锁，锁有三个位置，分别标记为1、2、3，转盘可向左(L)或向右(R)转动。这样，在任意时刻转盘都有6种可能的运动，即1L、1R、2L、2R、3L和3R。保险箱的组合密码是1L、3R、2L，转盘的任何其他运动都将引起报警。图4.1描绘了保险箱的状态转换情况。4.2有穷状态机4.2.1概念图4.1保险箱的状态转换图图4.1是一个有穷状态机的状态转换图。状态转换并不一定要用图形方式描述，表4.1（见书68页）的表格形式也可以表达同样的信息。从上面这个简单例子可以看出，一个有穷状态机包括下述5个部分：状态集J、输入集K、由当前状态和当前输入

5、确定下一个状态(次态)的转换函数T、初始态S和终态集F。对于保险箱的例子，相应的有穷状态机的各部分如下。状态集J：｛保险箱锁定，A，B，保险箱解锁，报警｝。输入集K：｛1L，1R，2L，2R，3L，3R｝。转换函数T：如表4.1所示。初始态S：保险箱锁定。终态集F：｛保险箱解锁，报警｝。如果使用更形式化的术语，一个有穷状态机可以表示为一个5元组(J，K，T，S，F)，其中：J是一个有穷的非空状态集；K是一个有穷的非空输入集；T是一个从(J-F)×K到J的转换函数；S∈J，是一个初始状态；FJ，是终态集。有穷状态机的概念在计算机系统中应用得非常广泛。例如，每个菜单驱

6、动的用户界面都是一个有穷状态机的实现。一个菜单的显示和一个状态相对应，键盘输入或用鼠标选择一个图标是使系统进入其他状态的一个事件。状态的每个转换都具有下面的形式：当前状态〔菜单〕+事件〔所选择的项〕下个状态。为了对一个系统进行规格说明，通常都需要对有穷状态机做一个很有用的扩展，即在前述的5元组中加入第6个组件——谓词集P，从而把有穷状态机扩展为一个6元组，其中每个谓词都是系统全局状态Y的函数。转换函数T现在是一个从(J-F)×K×P到J的函数。现在的转换规则形式如下：当前状态〔菜单〕+事件〔所选择的项〕+谓词下个状态。有限状态自动机（FSM"finitestat

7、emachine"或者FSA"finitestateautomaton"）是为研究有限内存的计算过程和某些语言类而抽象出的一种计算模型。有限状态自动机拥有有限数量的状态，每个状态可以迁移到零个或多个状态，输入字串决定执行哪个状态的迁移。有限状态自动机可以表示为一个有向图。有限状态自动机是自动机理论的研究对象。有多种类型的有限状态自动机：接受器判断是否接受输入；转换器对给定输入产生一个输出。常见的转换器有Moore机与Mealy机。Moore机对每一个状态都附加有输出动作，Mealy机对每一个转移都附加有输出动作。为了具体说明怎样用有穷状态机技术表达系统的规格说明