下载文档原格式
习题33-1 画出下列有限自动机的状态转换图，并说明它所识别或接受的语言是什么？①M＝({S，A，B，C}，{0，1}，f，S，{S})，其转换函数为：f(S，0)=B f(B，0)= Sf(S，1)=A f(B，1)= Cf(A，0)=C f(C，0)= Af(A，1)=S f(C，1)= B参考答案：有限自动机的状态转换图它所识别或接受的语言是：L(M)={ε,00,11,0101,0110,1001,1010,0011,0000,1111,…,}由偶数个0或偶数个1组成的二进制串。
②M＝({0，1，2}，{a，b}解答：有限自动机M的状态转换图：有限自动机M所识别或接受的语言是：L(M)={a,aaa,abaa,ba,baaa,babaa,…}3-2设计字母表∑={a,b}上的确定有限自动机，使它能识别或接受下列语言：①以aa为首的所有符号串集合；解答：正则式e=aa(a | b)*NFA：最小化：2习题来源：编译技术（王力红）习题解答：黎远松②以aa结尾的所有符号串集合；e=(a|b)*aa{X}为0{X,A}为1③含有相继两个a或相继两个b的所有符号串集合。
e=(a|b)*(aa|bb)(a|b)*3-3 试把下述NFA变换为DFA。
解答：最基本的方法是子集法：重命名：{0}为0，{1}为1，{1，2}为2，包含原终态2的{1，2}为新终态，于是所求DFA为：习题来源：编译技术（王力红）习题解答：黎远松解：最基本的方法：子集法：重命名：3-4 试把下列εFA变换为非εFA。
参考答案：习题来源：编译技术（王力红）习题解答：黎远松用子集法：3-5 试把下列FA确定化(若需要的话)和最小化。
参考答案：2,4状态是死状态，应删除。
只有一个状态的FA肯定是确定化的和最小化的。
习题来源：编译技术（王力红）习题解答：黎远松此FA是DFA，不需要确定化。
最小化：首先按终态与非终态划分：{0，1}，{2，3，4，5}；然后计算：对于输入a，b，{0，1}1等价。
进程状态转换图进程管理2011-06-28进程状态转换图进程管理进程状态转换图进程管理进程管理要点?基础：进程描述及控制?策略：进程调度?实现：互斥与同步?避免：死锁与饥饿?解决：几个经典问题?关于：进程通信进程的概念?现代操作系统的重要特点：程序的并发执行及系统所拥有的资源被共享和系统的用户随机地使用。
?操作系统的重要任务之一：使用户充分、有效地利用系统资源。
程序顺序执行?程序：源代码、目标程序和可执行程序?程序执行：编辑、编译、链接、执行?程序的结构：顺序结构、分支结构和循环结构。
进程的引入(一)?前趋图：是一个有向无环图。
图中的每个结点用于表示一条语句、一个程序段或进程；结点间的有向边表示在两个结点之间存在的偏序或前趋关系。
进程的引入(二)?程序顺序执行：是指若干个程序或程序段之间必须按照某种先后次序逐个执行，仅当前一项操作执行完成后，才能执行后继操作。
?程序顺序执行时具有以下特征：(1)顺序性(2)封闭性(3)确定性(4)可再现性进程的引入(三)?多道程序系统中程序执行环境的变化在许多情况下，需要计算机能够同时处理多个具有独立功能的程序。
批处理系统、分时系统、实时系统以及网络与分布式系统等都是这样的系统。
?执行环境具有三个特点：?独立性：每道程序都是逻辑上独立的，它们之间不存在逻辑上的制约关系。
?随机性：在多道程序环境下，特别是在多用户环境下，程序和数据的输入与执行开始时间都是随机的。
?资源共享：资源共享将导致对进程执行速度的制约。
进程的引入(四)?程序并发执行：是指两个或两个以上的程序或程序段可在同一时间间隔内同时执行。
?程序的并发执行卓有成效地提高了系统的吞吐量。
?程序并发执行的新特征：间断性；失去封闭性；不可再现性；资源共享；程序与计算不再一一对应。
进程的引入(五)?程序的并发执行可进一步分为两种：第一种是多道程序系统的程序执行环境变化所引起的多道程序的并发执行。
第二种并发执行是在某道程序的几个程序段中(例如几个程序)，包含着一部分可以同时执行或顺序颠倒执行的代码。
3、进程状态的切换图三态模型⼀个进程从创建⽽产⽣⾄撤销⽽消亡的整个⽣命周期，可以⽤⼀组状态加以刻划，根据三态模型，进程的⽣命周期可分为如下三种进程状态：1. 运⾏态(running):占有处理器正在运⾏2. 就绪态(ready):具备运⾏条件，等待系统分配处理器以便运⾏3. 等待态(blocked):不具备运⾏条件，正在等待某个事件的完成下⾯是三个状态的转换图：运⾏状态的进程将由于出现等待事件⽽进⼊等待状态，当等待事件结束之后等待状态的进程将进⼊就绪状态，⽽处理器的调度策略⼜会引起运⾏状态和就绪状态之间的切换。
引起进程状态转换的具体原因如下：运⾏态—→等待态：等待使⽤资源；如等待外设传输；等待⼈⼯⼲预。
等待态—→就绪态：资源得到满⾜；如外设传输结束；⼈⼯⼲预完成。
运⾏态—→就绪态：运⾏时间⽚到；出现有更⾼优先权进程。
就绪态—→运⾏态：CPU 空闲时选择⼀个就绪进程。
五态模型在⼀个实际的系统⾥进程的状态及其转换⽐上节叙述的会复杂⼀些，例如引⼊专门的新建态（new）和终⽌态（exit ）状态转换图如下所⽰：新建态对应于进程刚刚被创建的状态。
创建⼀个进程要通过两个步骤，1. 为⼀个新进程创建必要的管理信息，2. 让该进程进⼊就绪态。
此时进程将处于新建态，它并没有被提交执⾏，⽽是在等待操作系统完成创建进程的必要操作。
需要注意的是，操作系统有时将根据系统性能或主存容量的限制推迟新建态进程的提交类似地，进程的终⽌也要通过两个步骤，⾸先,是等待操作系统进⾏善后，然后,退出主存。
当⼀个进程到达了⾃然结束点，或是出现了⽆法克服的错误，或是被操作系统所终结，或是被其他有终⽌权的进程所终结，它将进⼊终⽌态。
进⼊终⽌态的进程以后不再执⾏，但依然临时保留在操作系统中等待善后。
⼀旦其他进程完成了对终⽌态进程的信息抽取之后，操作系统将删除该进程。
引起进程状态转换的具体原因如下：NULL—→新建态：执⾏⼀个程序，创建⼀个⼦进程。
