成都网站建设新网创想,佛山微网站开发哪家好,wordpress加上qq登录,宁波seo网络推广代理公司【软考】程序设计语言基础
一.程序设计语言基础概念
计算机要通过程序或指令来控制才能完成各种任务。程序设计语言#xff08;计算机语言#xff09;#xff1a;人与机器交换信息的语言。
1.程序设计语言
计算机语言大致分为机器语言、汇编语言和高级语言三种。机器语言…【软考】程序设计语言基础
一.程序设计语言基础概念
计算机要通过程序或指令来控制才能完成各种任务。程序设计语言计算机语言人与机器交换信息的语言。
1.程序设计语言
计算机语言大致分为机器语言、汇编语言和高级语言三种。机器语言是计算机可以直接理解和执行的二进制代码效率最高但难以编写。汇编语言用助记符代替机器指令可读性比机器语言强但仍与硬件紧密耦合。高级语言更接近自然语言如C、Python等可移植性好、易于维护但执行效率相对较低。编译型语言如C需要先将源代码全部编译成机器码再执行而解释型语言如Python则是一行一行解释执行前者执行效率更高后者更灵活。
机器语言低级语言汇编语言低级语言高级语言分为解释型语言和编译型语言
总结来说
机器语言 计算机的“母语”效率高但晦涩难懂。汇编语言 机器语言的“速记”可读性增强但仍依赖硬件。高级语言 人类友好的语言可移植性好但效率相对较低。编译型语言 先编译后执行效率高。解释型语言 边解释边执行灵活度高。
选择哪种语言取决于具体应用场景。 如果对性能要求极高可以选择机器语言或汇编语言如果开发效率和可维护性更重要可以选择高级语言如果需要快速开发原型或脚本解释型语言是不错的选择。
2.解释型语言和编译型语言
1、解释程序也称解释器;直接解释执行源程序或者将源程序翻译成某种中间代码后再加以执行 2、编译程序也称编译器;将源程序翻译成目标语言程序然后在计算机上运行目标程序。 3、两者的根本区别:编译方式下机器上运行的是与源程序等价的目标程序源程序和编译程序都不再参与目标程 序的执行过程因此执行时效率较高;解释方式下解释程序和源程序(或某种等价表示)要参与到程序的运行过 程中运行程序的控制权在解释程序边解释边执行执行效率较低。即:解释方式下翻译程序不生成独立的目 标程序而编译方式则生成独立保持的目标程序。 总结
编译得到目标代码直接执行。解释得到中间代码边解释边执行。编译型语言速度更高但是灵活性差解释型语言灵活性好但是速度相对较慢。我举个例子像C那种没办法写完直接在编译器里跑的就是编译型语言他会生成一个exe文件给你运行那像java或者python写完直接在解释器里跑就可以了。记住能一步到位直接跑的就是解释型写完还要打开个新文件的就是编译型语言。
3.常见程序设计语言的特点
(适当记忆看到了要能想起来这个东西是大概干嘛的就可以了)
Fortran语言(第一个高级程序设计语言科学计算执行效率高)
Pascal语言(结构化程序设计语言表达能力强Delphi)
C语言(通用、结构化程序设计语言指针操作能力强高效)
Lisp语言(函数式程序语言符号处理人工智能)
C语言(C语言基础上增加了类机制面向对象高效与C兼容)
Java语言(面向对象中间代码跨平台通用的程序设计语言)
Python(面向对象解释型程序设计语言胶水语言通用的脚本语言)
PHP(服务器端脚本语言制作动态网页)
Ruby(简单快捷面向对象脚本语言)
Delphi(快速应用程序开发工具可视化编程环境)
COBOL(数据处理领域最为广泛的程序设计语言高级编程语言)
XML(可扩展标记语言标准通用标记语言的子集)
PROLOG(逻辑式语言间接性表达能力强建造专家系统、数据库、自然语言理解、智能知识库等)
注:C/C常被用于操作系统开发;脚本语言是解释性语言。
4.程序语言设计的基础成分
4.1 程序设计语言的基本成分
程序设计语言作为人与计算机交流的工具其基本成分主要包括
数据 程序处理的对象包括各种类型的数据。运算 对数据进行操作包括算术运算、逻辑运算等。控制 控制程序执行的流程包括顺序结构、选择结构和循环结构。传输 数据在程序内部或不同程序之间传递。
4.2 程序设计语言的数据成分
4.2.1 C/C语言基本数据类型
数字类型 整型int、short、long、long long浮点型float、double、long double字符型char 布尔类型 bool指针类型 指向内存地址枚举类型 enum
4.2.2 Java语言基本数据类型
数字类型 byte、short、int、longfloat、doublechar 布尔类型 boolean引用类型 指向对象的引用
4.2.3 Python语言基本数据类型
不可变数据 Number数字int、float、complexString字符串由字符组成的序列Tuple元组有序不可变的元素集合 可变数据 List列表有序可变的元素集合Dictionary字典无序可变的键值对集合Set集合无序不可变的元素集合元素不重复
特性列表list元组tuple集合set字典dictionary字符串string有序性有序有序无序无序有序可变性可变不可变可变可变不可变元素唯一性允许重复允许重复不允许重复键唯一允许重复访问方式索引索引元素成员测试键索引常见操作append, insert, remove, pop, sort连接切片交集并集差集增删改查切片连接查找替换分割Java对应类型ArrayList, LinkedListArrayHashSet, TreeSetHashMap, TreeMapString
4.3运算成分
4.3.1 C/C语言运算符
算术运算符 、-、*、/、%、、–关系运算符 、!、、、、逻辑运算符 、||、!位运算符 、|、^、~、、赋值运算符 、、-、*、/、%、、|、^、、其他运算符 sizeof、取地址、*解引用、.成员访问、-指针成员访问
4.3.2 Java语言运算符
其他运算符 instanceof、new其他的运算符差不多
4.3.3 Python语言运算符
成员运算符 in、not in身份运算符 is、is not其他的运算符差不多
补充说明
Java的引用类型 Java中所有对象都是通过引用来访问的。Python的动态类型 Python变量不需要事先声明类型可以动态地改变类型。不同语言的数据类型表示方式可能不同
特性列表list元组tuple集合set字典dictionary字符串string定义有序可变的元素集合用方括号 [] 表示有序不可变的元素集合用圆括号 () 表示无序不重复的元素集合用大括号 {} 表示无序可变的键值对集合用大括号 {} 表示键必须唯一由字符组成的有序序列用单引号或双引号括起来元素类型任意数据类型可以重复任意数据类型可以重复任意不可变数据类型不能重复键必须是不可变数据类型如字符串、数字值可以是任意数据类型字符访问元素通过索引访问索引从 0 开始通过索引访问索引从 0 开始不能通过索引访问常用 in 操作符判断元素是否存在通过键访问值通过索引访问索引从 0 开始修改元素可以直接修改元素的值不能修改元素的值不能修改元素但可以添加或删除元素可以修改键对应的值也可以添加或删除键值对不可修改单个字符但可以创建新的字符串添加元素append()、insert() 等方法不能添加元素add() 方法keyvalue 的形式添加键值对不能直接添加通常通过连接操作创建新字符串删除元素remove()、pop() 等方法不能删除元素remove() 方法del 语句删除键值对不能删除单个字符但可以通过切片等操作创建新字符串长度len() 函数获取长度len() 函数获取长度len() 函数获取长度len() 函数获取键值对个数len() 函数获取字符个数排序可以排序不能排序元素无序键无序但值可以排序可以排序常见操作切片、连接、循环、排序等切片、连接、循环等交集、并集、差集等键的访问、值的修改等切片、连接、查找、替换、分割等应用场景存储有序可变的数据如列表、数组存储有序不可变的数据如常量、配置信息存储不重复的元素如去重、成员测试存储键值对如字典、配置文件存储文本信息如名字、地址、句子等
4.4 控制结构
程序的控制结构决定了程序执行的流程是程序设计中非常重要的概念。除了您提到的顺序结构、选择结构和循环结构外还有一些高级的控制结构如函数调用、异常处理等。
4.4.1 顺序结构
顺序结构是最简单的控制结构按照语句的书写顺序从上到下依次执行。
print(Colored)
print(Feather)4.4.2 选择结构
选择结构根据条件判断的结果选择不同的执行路径。常见的选择结构有
if语句 当条件为真时执行某个代码块。
age 18
if age 18:print(You are an adult.)if-else语句 当条件为真时执行一个代码块否则执行另一个代码块。
age 15
if age 18:print(You are an adult.)
else:print(You are a minor.)switch-case语句 根据表达式的值选择不同的代码块执行C/C、Java等语言支持。
4.1.3 循环结构
循环结构用于重复执行一段代码直到满足某个条件为止。常见的循环结构有
while循环 当条件为真时不断执行循环体。
count 0
while count 5:print(count)count 1for循环 一般用于遍历序列如列表、元组、字符串中的元素。
for i in range(5):print(i)do-while循环 先执行一次循环体再判断条件如果条件为真则继续执行。
4.1.4 其他控制结构
函数调用 将一段代码封装成函数通过函数名和参数调用。异常处理 处理程序运行时发生的异常保证程序的健壮性。跳转语句 如break、continue用于控制循环的执行。
4.1.5 控制结构的组合
在实际编程中各种控制结构可以相互嵌套、组合以实现复杂的逻辑。
# 嵌套循环
for i in range(3):for j in range(3):print(i, j)图示 总结
知道程序设计语言的基础成分以及Python中各种数据结构的区别就元组列表这些有什么共同点和不同点运算和控制了解一下就可以了。
5.函数的调用方式
5.1函数的格式
函数是组织代码的常用方式它将一段具有独立功能的代码块封装起来方便重复调用。
函数的一般格式如下
返回值类型 函数名(参数列表) {// 函数体
}返回值类型 函数执行完成后返回的值的类型。如果没有返回值则使用关键字void。函数名 函数的标识符用于调用函数。参数列表 函数接收的参数用逗号分隔。每个参数都有一个类型和一个名称。函数体 函数的具体实现包含一系列语句。
5.2函数的调用
函数的调用通过函数名并传递实际参数来实现。
函数名(实参1, 实参2, ...)5.3传值与传址
函数调用时参数的传递方式主要有两种传值和传址。
传值pass by value
概念 将实际参数的值复制一份传递给函数形参。特点 函数内部对形参的修改不会影响实参的值。示例
void swap(int a, int b) {int temp a;a b;b temp;
}int main() {int x 10, y 20;swap(x, y);cout x y endl; // 输出10 20
}在上面的例子中swap函数中的形参a和b是x和y的副本在函数内部交换a和b的值并不会影响x和y的值。
传址pass by reference
概念 将实际参数的地址传递给函数形参。特点 函数内部对形参的修改会直接影响实参的值。示例
void swap(int *a, int *b) {int temp *a;*a *b;*b temp;
}int main() {int x 10, y 20;swap(x, y);cout x y endl; // 输出20 10
}在上面的例子中swap函数的形参a和b是指向x和y的指针在函数内部通过指针修改了x和y的值。
5.4传值与传址的对比
特点传值传址参数传递方式将实际参数的值复制一份将实际参数的地址传递给形参函数内部对参数的修改不影响实参影响实参使用场景一般情况下如果函数不需要修改实参的值使用传值当函数需要修改实参的值时使用传址
总结
知道传值与传址的对比并且要看得明白具体题目那个值是怎么传的理解传值与传址的对比传值就好比你去copy一份别人电脑的数据过来你怎么折腾都不会影响别人电脑的内容传地址就好比你直接在别人的电脑上折腾影响这台电脑下一次copy给别人的值。
二.语言处理程序
1.编译过程概述
(要了解每个阶段都在干嘛错误分析阶段要学会判断归属)
其中无论是编译型还是解释型错误分析都是必须做的语法分析词法分析语意分析而中间代码生成和代码优化是看情况来的可做可不做。出错处理和符号表管理贯穿全程会在符号表中处理。 编译过程将高级语言编写的源代码转换为计算机能够直接执行的机器码。整个过程可以分为以下几个阶段
1. 1词法分析 (Lexical Analysis)
是编译过程的第一阶段其任务是对源程序从前到后(从左到右)逐个字符扫描从中识别出 一个个“单词”符号。词法分析过程的依据是语言的词法规则即描述“单词”结构的规则。 输入: 源程序的字符序列 输出: 记号流 (Token Stream) 任务: 从左到右逐个扫描源程序的字符。识别出有意义的最小单位——单词符号Token如关键字、标识符、常量、运算符、分隔符等。去除源程序中的注释和空白符。 示例: 这个就是看你拼写上有没有问题会不会出现什么非法字符什么的。 源代码VAR XY,Z:real; X:YZ*60;
记号流VAR, XY, , Z, :, real, ;, X, :, Y, , Z, *, 60, ;常用方法
有限自动机Finite Automata用于识别词法单元tokens有限自动机可以是确定的有限自动机DFA或非确定的有限自动机NFA。正则表达式Regular Expressions用于定义词法单元的模式正则表达式可以转换为有限自动机。词法生成器Lexer Generators如Flex它们使用正则表达式来生成词法分析器的代码。
1.2语法分析 (Syntax Analysis)
其任务是在词法分析的基础上根据语言的语法规则将单词符号序列分解成各类语法单位。通常语法分析是确定整个输入串是否构成一个语法上正确的程序。一般来说通过编译的程序不存在语法上的错误。 输入: 记号流 输出: 语法分析树 (Parse Tree) 或语法分析表 任务: 根据语言的语法规则将记号流组织成语法结构如表达式、语句、函数等。检查源程序是否符合语法规则。 示例: 这个更多体现在你的命名是否合法或者说你的数据类型是否正确比如说你用来放整数就用int别用double这种以及像9a这种以数字开头的非法命名等还有其他结构上比如循环结构if…end if不匹配缺少分号、括号不匹配、表达式缺少操作数等。
常用方法
上下文无关文法Context-Free Grammar, CFG用于描述编程语言的语法结构。递归下降解析器Recursive Descent Parsers一种自顶向下的解析方法通过递归函数调用实现。LL解析器LL Parsers预测分析的一种形式从左到右读取输入并从左端进行最左推导。LR解析器LR Parsers从左到右读取输入并从右端进行推导如SLR(1)、LALR(1)、LR(1)解析器。
1.3 语义分析 (Semantic Analysis)
其任务主要检査源程序是否包含静态语义错误(动态语义错误在执行过程中才能发现)并收集类型信息供后面的代码生成阶段使用。语义分析的一个主要工作是进行类型分析和检查。 输入: 语法分析树 输出: 带有类型信息的语法分析树或中间代码 任务: 检查程序的静态语义错误如类型不匹配、变量未声明、数组越界等。收集类型信息为后面的代码生成做准备。进行类型检查和转换。 示例: 运算符和运算类型不符合如取余时用浮点数再比如字符串的拼接“Colored”“Feathers”可以但是如果换成-号就不行了会报错这些东西会在静态语义分析阶段就会报错。 检查 X:YZ*60; 中变量 X, Y, Z 的类型是否为 real运算符 , * 是否适用于 real 类型。
特点静态语义分析动态语义分析执行时间编译期间运行期间检查对象程序的结构和类型程序的运行时行为发现错误类型类型错误、语法错误、未声明变量等空指针引用、数组越界、除以零等局限性无法发现所有错误例如运行时产生的错误需要在运行时执行效率较低
常用方法
属性文法Attribute Grammars用于定义和计算语言结构上的属性。类型检查Type Checking确保操作数类型正确变量在使用前已声明等。符号表Symbol Table用于存储变量名、函数名、类名等标识符的信息以及它们的属性。
1.4中间代码生成 (Intermediate Code Generation)
其任务是根据语义分析的输出生成中间代码。此阶段不是必须的。常见的中间代码有:树、后缀式、三地址码(四元式)。 输入: 带有类型信息的语法分析树 输出: 中间代码 (Intermediate Code) 任务: 将语法分析树转换为一种机器无关的中间表示形式如后缀式、三地址码、四元式、树等。中间代码更易于优化和生成目标代码。 示例: 三地址码 t1 : Z * 60
t2 : Y t1
X : t2常用方法
三地址代码Three-Address Code一种简化的机器无关的中间表示形式。抽象语法树Abstract Syntax Tree, AST表示源代码的抽象语法结构的树形结构。
1.5 代码优化 (Code Optimization)
其任务是优化中间代码。此阶段不是必须的。
输入: 中间代码输出: 优化后的中间代码任务: 对中间代码进行优化提高目标代码的执行效率。常见的优化技术有常量折叠、公共子表达式消除、死代码消除等。 示例: 如果 Z 的值在程序中始终为常数那么 Z * 60 可以提前计算。
常用方法
数据流分析Data Flow Analysis分析程序中变量的定义和使用以优化代码。控制流分析Control Flow Analysis分析程序的控制结构以优化代码。变换规则Transformation Rules用于转换程序代码以改善性能和效率。
1.6 目标代码生成 (Code Generation)
是编译器工作的最后一个阶段。其任务是把中间代码变换成特定机器上的绝对指令代码、可重定位的指令代码或汇编指令代码。本阶段与具体机器密切相关。 输入: 优化后的中间代码 输出: 目标机器代码 任务: 将优化后的中间代码翻译成特定机器的机器指令。 示例: x86汇编代码 MOV EAX, [Z] ; 将Z的值加载到EAX寄存器
IMUL EAX, 60 ; EAX EAX * 60
ADD EAX, [Y] ; EAX EAX Y
MOV [X], EAX ; 将EAX的值存入X常用方法
目标代码优化Target Code Optimization针对特定目标机器的代码优化。寄存器分配Register Allocation将变量映射到处理器的寄存器。指令选择Instruction Selection将中间代码映射到目标机器的指令集。
总结
编译过程是一个将高级语言转换为机器语言的过程每个阶段都有其特定的任务。通过词法分析、语法分析、语义分析等阶段编译器逐步将源代码转化为机器可执行的指令考试能知道什么问题在哪个阶段能被看出来就够了大致了解一下各阶段的常用方法。
补充几点
1.自顶向下(或自上而下) 分析法【递归下降分析法、预测分析法都是自顶向下的分析方法。】自底向上语法分析方法(移进归约分析法)、
2.符号表的作用是记录源程序中各个符号的必要信息以辅助语义的正确性检查和代码生成在编译过程中需要对符号表进行快速有效地查找、插入、修改和删除等操作。符号表的存在可以贯穿编译所有阶段。
3.错误管理 **静态错误:**编译时所发现的程序错误分为语法错误和静态语义错误, **语法错误包含:**单词拼写错误、标点符号错误、表达式中缺少操作数、括号不匹配等有关语言结构上的错误。【单词拼写错误、标点符号错误(中文符号等)属于词法错误;缺少分号、缺少括号、缺少操作数属于语法错误。】 **静态语义分析:**运算符与运算对象类型不合法等错误。 **动态错误:**发生在程序运行时也叫动态语义错误。包括死循环、变量取零时做除数、引用数组元素下标越界等错 误。
二.文法
文法速通
会推会做题就行
我举个例子比如文法G({a,b},{S,A},S,P),其中S能推出aAS|aA能推出SbA|SS|ba请你来构造句型aabAa的推导树如下图所示。从一开始的S开始慢慢去构造一开始S推aAS这样我们就完成了a的构造然后再看剩下的ASASA可以推SbA这样S就可以变成a我们就可以得到aabASS可以推a这样就可以得到aabAa了。 如果看不懂我给你说详细点
首先我们要构造的句型是aabAa使用的文法G({a,b},{S,A},S,P)其中产生式规则P如下
S → aAS | aA → SbA | SS | ba
下面是构造句型aabAa的详细步骤
从起始符号S开始我们选择产生式S → aAS这样我们得到了句型aAS。这一步我们完成了第一个字符’a’的构造。接下来我们需要处理剩下的部分AS。我们选择A的产生式A → SbA将A替换为SbA得到句型aaSbAS。现在我们关注第二个S我们再次使用S的产生式S → a将S替换为’a’得到句型aabAS。最后我们处理剩下的部分AS。我们选择A的产生式A → ba将A替换为’ba’得到最终的句型aabAa。
综上所述通过以下步骤我们构造出了句型aabAa
S → aAS → aaaSbAS → aabaAS → aabAa
如果想看文法相关的概念就继续往下看就好了。
1.什么是文法
在计算机科学中尤其是编译原理领域文法是一种用来描述形式语言的工具。它通过一系列规则定义了语言中所有合法句子的结构。这些规则通常以产生式的方式给出描述了如何从起始符号开始逐步生成语言中的句子。
2.文法的组成部分
终结符: 语言中最小的不可再分的符号它们构成了句子的基本元素。例如在编程语言中关键字、标识符、常量等都是终结符。非终结符: 表示语法结构的符号它们可以被替换成更小的子结构。通常用大写字母表示。产生式: 描述了非终结符如何被替换成更小的子结构或终结符的规则。开始符号: 文法中唯一的非终结符表示整个句子的开始。
3.文法的类型
根据产生式的形式文法可以分为不同的类型
0型文法: 最一般的文法形式没有限制。1型文法: 上下文敏感文法产生式的左部和右部长度存在限制。2型文法: 上下文无关文法产生式的左部只有一个非终结符。3型文法: 正则文法产生式的右部最多有一个非终结符并且位于开头或结尾。
4.上下文无关文法Context-Free Grammar, CFG
上下文无关文法是编译原理中最常用的文法类型。它的产生式形式为
A - α其中A 是非终结符α 是由终结符和非终结符组成的字符串。
示例
一个简单的算术表达式的上下文无关文法
E - E T | E - T | T
T - T * F | T / F | F
F - ( E ) | id | num其中
E表达式T项F因子id标识符num数字*
5.语法分析
语法分析是编译过程中的一个重要阶段它的任务是根据文法规则分析输入的字符串是否符合该文法。常用的语法分析方法有
自顶向下分析: 从文法的开始符号出发逐步向下推导直到匹配输入字符串。自底向上分析: 从输入字符串出发逐步向上归约直到归约到文法的开始符号。
6.文法在编译原理中的应用
语法定义: 文法用来精确地定义编程语言的语法结构。语法分析: 编译器通过语法分析器根据文法规则检查源程序的语法正确性。代码生成: 语法分析树可以作为代码生成阶段的输入生成目标代码。
总结
文法是描述形式语言的强大工具。通过文法我们可以精确地定义编程语言的语法并进行语法分析。上下文无关文法是编译原理中最常用的文法类型。理解文法的概念和应用对于深入学习编译原理具有重要意义。但是对于考试来说你要能理解能算就够了。
三.正规式与正规集
速通正规式与正规集
这个考的挺简单的我给你举个例子
由字符a、b构成的字符串中若每个a后至少跟子个b则该字符串集合可用正规式表示为()。
A.(b|ab)* B.(ab*)* C.(a*b*)* D.(a|b)*我个人觉得这个还是蛮简单的选A,每个a后面要有个b那么就a肯定不会单独出现所以CD就错了b可以自己出现所以B排除就选A咯如果看懂了的话这部分内容就可以了不懂或者想多学点就继续往下看吧。
正规式Regular Expression和正规集Regular Set是形式语言和编译原理中的基本概念。下面分别讲述它们的相关内容并提供适当的例子。
1.正规式Regular Expression
正规式是一个用于描述字符串集合的数学表达式它由以下元素组成
字母表中的单个字符例如a, b, 0, 1空字符串 ε表示没有任何字符的字符串并运算符 ∪表示选择“或”连接运算符通常省略不写表示字符串的连接闭包运算符 *表示零次或多次重复
正规式的运算规则如下
字母表中的字符本身是一个正规式它所表示的正规集就是包含该字符的集合。ε 是一个正规式它所表示的正规集只包含空字符串 ε。如果 r 和 s 是正规式那么 r∪s、rs 和 r* 也是正规式分别表示它们的并集、连接和闭包。
2.正规集Regular Set
正规集是由正规式定义的字符串集合。换句话说正规集是可以通过正规式来描述的所有可能字符串的集合。
举个例子假设字母表为 Σ {a, b}以下是一些正规式和它们对应的正规集的例子
正规式正规集描述具体例子假设字母表为{a, b}a包含单个字符 ‘a’ 的集合{a}ε只包含空字符串 ε 的集合{ε}a∪b包含字符 ‘a’ 或 ‘b’ 的集合{a, b}ab包含字符串 “ab” 的集合{ab}a*包含零个或多个 ‘a’ 的字符串集合{ε, a, aa, aaa, …}(a∪b)*包含任意由 ‘a’ 和 ‘b’ 组成的字符串集合{ε, a, b, aa, ab, ba, bb, aaa, aab, …}a*b以零个或多个 ‘a’ 开头后接 ‘b’ 的字符串集合{b, ab, aab, aaab, …}(ab)*包含零个或多个 “ab” 序列的字符串集合{ε, ab, abab, ababab, …}
四.有限自动机
速通有限自动机
这种题一般都会给你个图然后去让你分析你要看什么东西能到末状态
举个例子比如下面这张图其中A是起始状态C是末状态也就是结束状态。从A开始看也就是蓝线部分是1是0是无法确定的而观察红线部分如果要到达结束状态那么这个结尾肯定是。所以选项D结尾不一定是1所以排除D然后再看开头部分可以以1开始也可以以10、010、10、110开始都行但是B,C,D都是1一定在0的前面这是不对的所以这道题选A。其实题选什么不重要主要是要学会先分析结尾字符一定以什么结尾再分析起始字符如果实在不行再代入也是可以的
下图所示为一个有限自动机(其中A是初态、C是终态)该自动机识别的语言可用正规式()表示。
A.(0|1)*01 B.1*0*10*1 C.1*(0)*01 D.1*(0|10)*1*再举一个简单点的例子
下图所示为一个不确定有限自动机(NFA)的状态转换图。该NFA可识别字符串()。
A、0110
B、0101
C、1100
D、1010和上面一样先分析结尾肯定是以0结束所以B排除开头以0开头所以CD排除剩下A就是对的。如果遇到排完还有其他选项你就代入进去看看就知道了。 1.基本定义
有限自动机Finite Automaton是理论计算机科学中的一个基本概念它是计算理论中的一个抽象模型用来进行字符串的识别和处理。有限自动机广泛应用于自然语言处理、编译原理、网络协议、软件工程等领域。以下是有限自动机的相关概念及内容
M(S,∑, δ,S0,Z) 1)S是一个有限集每个元素为一个状态 2)∑是一个有穷字母表每个元素为一个输入字符 3)8是转换函数:是一个单值对照 4)S0,属于S是其唯一的初态 5)Z是一个终态集(可空) 2.分类
有限自动机能够识别的串:从初态出发可以到达终态且停留在终态 **确定的有限自动机:**当一个状态面对一个输入符号的时候所转换到的是一个唯一确定的状态。 **不确定的有限自动机:**当一个状态面对一个输入符号的时候它所转换到的可能不只一个状态可以是一个状态集合
3.特点
有限自动机的状态数是有限的。有限自动机在任一时刻只处于一个状态。有限自动机的下一个状态完全由当前状态和当前输入决定。
4.运行方式
有限自动机的运行过程可以看作是在输入字符串上的一个动作序列
开始时自动机处于初始状态 s0s0。逐个读取输入字符串中的符号。根据当前状态和输入符号使用状态转移函数 δδ 转移到下一个状态。重复步骤 2 和 3直到输入字符串结束。如果最后自动机处于一个终止状态则称该自动机接受了这个字符串否则字符串被拒绝。
5.应用
模式匹配例如正则表达式引擎可以用有限自动机实现。文本分析用于语言识别、词法分析等。协议解析网络协议中的状态管理。
6.与其他计算模型的比较
有限自动机是计算模型中最基本的一种它的计算能力弱于图灵机但强于更简单的模型如有限状态机 FSM它没有输入字母表的概念。DFA 和 NFA 在计算能力上是等价的即任何 NFA 都可以转换成等价的 DFA。
有限自动机的理论研究和实际应用对于理解计算机科学中的基本概念和设计高效算法都具有重要的意义。
五.表达式
表达式速通
要会画图分析就可以了
写这种表达式的题的时候最好把图画出来这样容易看很多也有一些小技巧我举个例子比如说A*BC-D花出来图就下面这个样子然后其中蓝色球按顺序连起来就是前序遍历黄色球连起来就是中序遍历红色球连起来就是后续遍历如果听不懂就看下面的图或者其他例子吧。 前序遍历示图其他的也一样蓝线进过蓝球的顺序就是前序遍历再换一条线连接黄色球就是中序遍历一样也可以求出后序遍历你要是不信你可以用你的方法验证一下。 如果看不懂上面在说什么就从这里开始学吧前序遍历、中序遍历和后序遍历是二叉树遍历的三种方式它们分别按照不同的顺序访问二叉树的节点。下面分别介绍这三种遍历方式
1.前序遍历Pre-order Traversal
前序遍历的顺序是先访问根节点然后递归地遍历左子树最后递归地遍历右子树。具体步骤如下
访问根节点前序遍历左子树前序遍历右子树。
例如对于以下二叉树 A/ \B C/ \ \
D E F前序遍历的结果为A - B - D - E - C - F
2.中序遍历In-order Traversal
中序遍历的顺序是先递归地遍历左子树然后访问根节点最后递归地遍历右子树。具体步骤如下
中序遍历左子树访问根节点中序遍历右子树。
以上述二叉树为例中序遍历的结果为D - B - E - A - C - F
3.后序遍历Post-order Traversal
后序遍历的顺序是先递归地遍历左子树然后递归地遍历右子树最后访问根节点。具体步骤如下
后序遍历左子树后序遍历右子树访问根节点。
以上述二叉树为例后序遍历的结果为D - E - B - F - C - A
这三种遍历方式在二叉树的操作中非常常见它们可以用于查找、插入、删除等操作。不同的遍历方式适用于不同的场景例如前序遍历常用于复制二叉树中序遍历常用于二叉搜索树的中序遍历结果为有序序列后序遍历常用于删除二叉树。
总结
mg-dgP72RJ5-1726151377708)]
如果看不懂上面在说什么就从这里开始学吧前序遍历、中序遍历和后序遍历是二叉树遍历的三种方式它们分别按照不同的顺序访问二叉树的节点。下面分别介绍这三种遍历方式
1.前序遍历Pre-order Traversal
前序遍历的顺序是先访问根节点然后递归地遍历左子树最后递归地遍历右子树。具体步骤如下
访问根节点前序遍历左子树前序遍历右子树。
例如对于以下二叉树 A/ \B C/ \ \
D E F前序遍历的结果为A - B - D - E - C - F
2.中序遍历In-order Traversal
中序遍历的顺序是先递归地遍历左子树然后访问根节点最后递归地遍历右子树。具体步骤如下
中序遍历左子树访问根节点中序遍历右子树。
以上述二叉树为例中序遍历的结果为D - B - E - A - C - F
3.后序遍历Post-order Traversal
后序遍历的顺序是先递归地遍历左子树然后递归地遍历右子树最后访问根节点。具体步骤如下
后序遍历左子树后序遍历右子树访问根节点。
以上述二叉树为例后序遍历的结果为D - E - B - F - C - A
这三种遍历方式在二叉树的操作中非常常见它们可以用于查找、插入、删除等操作。不同的遍历方式适用于不同的场景例如前序遍历常用于复制二叉树中序遍历常用于二叉搜索树的中序遍历结果为有序序列后序遍历常用于删除二叉树。
总结
这三种遍历方式在二叉树的操作中非常常见它们可以用于查找、插入、删除等操作。不同的遍历方式适用于不同的场景例如前序遍历常用于复制二叉树中序遍历常用于二叉搜索树的中序遍历结果为有序序列后序遍历常用于删除二叉树。三种遍历方式的相互转换学会画图推断。
