第三章名词解释.docx

《第三章名词解释.docx》由会员分享，可在线阅读，更多相关《第三章名词解释.docx（4页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、【精品文档】如有侵权，请联系网站删除，仅供学习与交流第三章名词解释.精品文档.第三章 名词解释1.最小化（minimize）指DFA M状态数的最小化，是指构造一个等价的DFA M，而后者有最小的状态。2.标示符（IDentifier）是指用来标识某个实体的一个符号。在不同的应用环境下有不同的含义。3.正规表达式（regular expression）是说明单词的模式(pattern)的一种重要的表示法（记号），是定义正规集的工具。4.正规式（Normal form）正规式也称正则表达式，也是表示正规集的数学工具。5.正规集（Normal set）如果把每类单词视作一种语言，那么每一类单词的全

2、体单词组成了相应的正规集。6. 有限状态自动机（finite state automaton）有限状态自动机拥有有限数量的状态，每个状态可以迁移到零个或多个状态，输入字串决定执行哪个状态的迁移。有限状态自动机可以表示为一个有向图。有限状态自动机是自动机理论的研究对象。7. 词法分析器（Lexical analyzer）词法分析是指将我们编写的文本代码流解析为一个一个的记号，分析得到的记号以供后续语法分析使用。8. 确定的有限自动机（DFA: Deterministic Finite Automata）自动机的每个状态都有对字母表中所有符号的转移。9.五元式（Five element type）

3、由五个要素组成的式子：由有限个状态组成的集合：由有限个输入字符组成的字母表：从到的单值映射，指明当前态为p，输入字符a，下一个状态为q：一个属于K的特定状态，称之为初始状态：若干个属于K的特定状态，它们组成的集合称之为终态集，记为Z。10.非确定的有限自动机(NFA：Non deterministic finite automaton)自动机的状态对字母表中的每个符号可以有也可以没有转移，对一个符号甚至可以有多个转移。自动机接受一个字，如果存在至少一个从 q0 到 F 中标记(label)著这个输入字的一个状态的路径。如果一个转移是未定义的，自动机因此不知道如何继续读取输入，则拒绝这个字。11

4、. 接受集（L（M）,Receiving set）对于*中的符号串X，若集合f（ ，x）中含有属于终态集Z中的状态（即至少存在一条从 到 某一终态的通道，吧此通道中所有矢线上的标记连接起来就是符号串x），我们就说x为M所接受，所有这样的x所组成的集合称为NFA M的接受集，记做L（M）。即L（M）=x|f（ ，x）ZU，x*）12.映射（mapping）指两个元素的集之间元素相互“对应”的关系13.贪心算法（greedy algorithm）在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的是在某种意义上的局部最优解。14. 分隔符(Separator

5、)标识文字分隔的位置15.子集（subset）如果集合A的任意一个元素都是集合B的元素（任意aA则aB），那么集合A称为集合B的子集（subset）。16.字符集（Character set）是多个字符的集合，字符集种类较多，每个字符集包含的字符个数不同，常见字符集名称：ASCII字符集、GB2312字符集、BIG5字符集、 GB18030字符集、Unicode字符集等。17.线性方程（linear equation）线性方程也称一次方程。指未知数都是一次的方程。其一般的形式是ax+by+.+cz+d=0。18.保留字（Reserved word）指在高级语言中已经定义过的字，使用者不能再将这

6、些字作为变量名或过程名使用。19.状态转换图（State transition diagram）通过描绘系统的状态及引起系统状态转换的事件，来表示系统的行为。此外状态转换图还指明了作为特定事件的结果系统将做哪些动作（例如，处理数据）。因此状态转换图提供了行为建模机制。20.定义域（domain of function）是函数三要素(定义域、值域、对应法则）之一，对应法则的作用对象。求函数定义域主要包括三种题型：抽象函数，一般函数，函数应用题。含义是指自变量 x的取值范围。21.类别码（Classification Code）按照信息分类编码的结果，利用一个或一组数字、字符，或数字字符混合标记不

7、同类别信息的代码。22.数制转换（Number System Conversion）各类数制之间的转换。比如10进制，2进制，8进制，16进制之间的转换。23.目标代码（object code）指计算机科学中编译器或汇编器处理源代码后所生成的代码，它一般由机器代码或接近于机器语言的代码组成。24.驱动程序（Device Driver）是一种可以使计算机和设备通信的特殊程序。相当于硬件的接口，操作系统只有通过这个接口，才能控制硬件设备的工作。25.词型（token pattern）一个正规式Ri，用来描述一种单词的结构。27.正规文法（formal grammar）正规文法是左线性文法和右线性文

8、法的统称。它们都是Chomsky分类下的3型文法。由正规文法产生的语言称为正规集。27.右线性文法（right-linear grammar）设GS=(VN，VT，P，S)为CFG，若P中的产生或均有如下的形式：AaB或Aa（AVN，aVT）则称G为右线性文法。28.左线性文法（left-linear grammar）若一个文法GS=(VN，VT，P，S)中的产生式均有如下的形式：ABa或Aa（A，BVN，aVT）则称G为左线性文法。29.状态转换矩阵（state transition matrix）在计算机内，实现状态转换图的方法之一，是以状态图中的各个状态S1,S2,，Sn为行，以可能输入

9、的各个输入符号a1,a2,，am为列，组成一个n行m列的矩阵：B=a1a2amS1S2SnB11B12B1mB21B22B2mBn1Bn2Bnm这个矩阵被称为状态转换矩阵或简称为状态矩阵30.字符串（string）是由数字、字母、下划线组成的一串字符。31.正规文法（regular grammer）：左线性文法和右线性文法的统称.它们都是Chomsky分类下的3型文法.由正规文法产生的语言称为正规集.下面我们将会看到,这里之所以用“正规”二字为一种语言命名,是因为这种语言的结构可以用所谓正规式来描述.32. Thompson法：由正规式构造出FA的方法。所构造的FA均是一个含有动作的NFA，其

10、中只有一个初态和一个终态，而从终态不再有任何射出矢线。33.单词（token）:对程序语言来说，关键字（如if,for,while,begin,end等）、标识符、各种常数、各种运算符（如+、*、=、+=、等）及分隔符（如逗号、冒号、分号及括号等）都是单词。34.词文（lexeme）：构成各个单词的字符串35.分配单位（allocation unit）：直接从磁盘中读取的最小字节数36.LEX：一种供编译程序开发者使用的工作语言以及此语言的翻译程序所组成的系统。它是由美国Bell实验室M.Lesk等人用C语言研制的一个词法分析程序的自动生成工具。37.FA(Finite Automaton）：

11、由于NFA与DFA接收相同的语言类，因此有些时候在无特定要求的情况下，可以不对NFA和DFA加以区分，而统称为FA。38.终态 (finalstate)NFA确定化的时候，包含NFA初态的那个DFA状态就是确定后的DFA的初态DFA的终态就是所有包含了NFA终态的DFA的状态.39.状态矩阵 (statematrix)以状态转换图中的各个状态的s1.s2.sn为行，以可能输入的各个输入符号a1.a2.an为列组成一个n行m列的矩阵。40.扫描器(scanner) 扫描器是一类自动检测本地或远程主机安全弱点的程序，它能够快速的准确的发现扫描目标存在的漏洞并提供给使用者扫描结果。工作原理是扫描器向目标计算机发送数据包，然后根据对方反馈的信息来判断对方的操作系统类型、开发端口、提供的服务等敏感信息.