软件工程专业期中复习题

软件工程本科《软件形式化方法》期中复习题（闭卷）1.（1）何谓软件？软件的本质特性是什么？软件技术发展主要驱动力是什么？软件是客观世界中问题空间与解空间的具体描述，是追求表达能力强、更符合人类思维模式，具有易构造性和易演化性的计算模型。软件的本质特性是构造性和演化性。从操作系统发展的角度来看，随着计算机环境的变化，软件技术在更大范围内促进了资源共享。从软硬件异构性角度来看，为了尽可能平滑地桥接异构性，增加互操作性，为了屏蔽计算机软件异构性发明了操作系统，为了屏蔽操作系统的异构性发展了中间软件，我为了屏蔽中间件的多样性和异构性发展了Web技术，因此软件技术的发展本身就是一个不断桥接异构性的过程，实质上是解决概念和处理逻辑之间的问题。从软件生产方式的角度来看，为了尽可能多的凝练共性，降低开发应用软件的复杂度，提高软件开发效率和质量，而发展了软件的技术。（2）简述软件工程的主要研究内容和主要发展历程；简述我国软件工程的发展历程和代表性研究工作。主要发展历程：从60年代到90年代，60年代还是手编程序，当时应用在不断的发展，手编程序需要大量的人参与，所以出现了软件危机，软件工程被正式提出来。开始注重程序结构的研究，程序设计语言和编辑系统得到了应用。到了70年代出现了结构化分析和设计方法，程序设计方法学成为研究热点，到80年代CASE工具和环境的研制成为热点，面向对象技术开始出现并逐步流行。到了90年代软件复用和软件构件技术得到广泛的应用。我国软件工程的发展历程：为了满足中国软件产业发展的需求，中国1980年启动软件工程与实践，80年代开展软件开发方法学研究，CASE无共聚合环境的研发，软件产业开始起步，但是开发停留在手工作坊式。到了90年代，以构件技术为主线开展了前沿的研究，而且开始建立较为全面的软件工程环境，软件企业也开始使用软件工具。2000年展开网构软件技术体系的研究，建立软件构件库体系和标准和人才培养，软件企业开始尝试工业化生产技术。代表性研究工作：一、软件自动化系统，由南京大学徐家福教授领导科研团队做的工作。第二、XYZ系统，由中科院堂稚松院士领导的科研团队，XYZE是第一个可执行的使序逻辑语言。第三、中科院董韫美院士做的工作。第四个是青鸟工程。2.（1）试阐述形式化方法的概念与主要内容。试阐述模型检测的概念。模型检测：主要通过显式状态搜索或隐式不动点计算来验证有穷状态并发系统的模态/命题性质（2）试分别阐述形式语言和自动机的概念与分类。形式语言：按一定规律构成的句子或符号串的有限或无限的集合自动机概念：自动机是有限状态机(FSM)的数学模型分类：确定有限自动机(DFA)；非确定有限自动机(NFA)；有ε转移的非确定有限自动机(FND-ε或ε-NFA)；非标自动机；（3）简述有限状态自动机接受的语言与正则表达式之间的关系。正则表达式可以表达正则语言，精确的是可被有限状态自动机接受的语言类。但是在简洁性上有重要区别。某类正则语言只能用大小指数增长的自动机来描述，而要求的正则表达式的长度只线性的增长。(4)简述文法的乔姆斯基体系。是刻画形式文法表达能力的一个分类谱系层次：0-型文法（无限制文法或短语结构文法）包括所有的文法；1-型文法（上下文相关文法）生成上下文相关语言；2-型文法生成上下文无关语言；3-型文法（正规文法）生成正规语言。（5）如何将NFA转换为DFA？如何将3型语言转换为有穷自动机？NFA转DFA的关键1、符号合并smove(S,a)从S出发，边为a的状态集需要合并为一个。2、λ合并将带有空边的状态合并NFA到DFA的转换过程:1.NFA初始状态集的λ合并集作为DFA的初始状态。2.对DFA中一状态S，对a∈∑,进行符号合并和λ合并得到的状态设为S’,定义DFA的转换函数为f(S,a)=S’.3.直至没有新状态产生为止。（6）什么是时序逻辑？试阐述其语法和语义。时序逻辑也叫时态逻辑，由多个触发器和多个组合逻辑块组成的网络。时序逻辑被用来描述为表现和推理关于时间限定的命题的规则和符号化的任何系统，主要用于形式验证。3.试简要阐述下面有关形式化方法的概念：（1）形式化规约：对程序“做什么”(whattodo)的数学描述,是用具有精确语义的形式语言书写的程序功能描述,它是设计和编制程序的出发点,也是验证程序是否正确的依据（2）形式化验证：根据某个或某些形式规范或属性，使用数学的方法证明其正确性或非正确性（3）模型检测：主要通过显式状态搜索或隐式不动点计算来验证有穷状态并发系统的模态/命题性质（4）混成自动机：是具有一类同时离散和连续行为特征的复杂系统的自动机（5）时序逻辑：时序逻辑也叫时态逻辑，由多个触发器和多个组合逻辑块组成的网络。时序逻辑被用来描述为表现和推理关于时间限定的命题的规则和符号化的任何系统，主要用于形式验证。（6）Petri网：Petri网是对离散并行系统的数学表示4．构造有穷自动机（画出状态转移图），使之接受下列语言：（1）．含有连续的三个0的0，1串（2）．以连续的三个0结尾的0，1串5．设NFAM=（Q，Σ，δ，q0,F）,其中：Q={q0,q},Σ={a,b},F={q},δ(q0,a)={q0,q},δ(q0,b)={q},δ(q,a)=φ,δ(q,b)={q0,q}。（1）试构造与之等价的DFAMD（2）试构造与之等价的正则文法。6.设计一个智能控制灯，在按下开关后低亮，若之后3秒内再按开关则高亮，反之超过3秒不按开关则自动关灯，高亮后3秒后则自动关灯，请用时间自动机表达上述行为模型。