符号串

编译原理_平时作业1 对于下列语言分别写出它们的正规表达式。

(1) 英文字母组成的所有符号串，要求符号串中顺序包含五个元音。

答：令Letter表示除这五个元音外的其它字母。

((letter)*A(letter)*E(letter)*I(letter)*O(letter)*U(letter))*(2) 英文字母组成的所有符号串，要求符号串中的字母依照词典顺序排列。

答：A*B*....Z*(3) Σ={0,1}上的含偶数个1的所有串。

答： (0|10*1)*(4) Σ={0,1}上的含奇数个1的所有串。

答：(0|10*1)*1(5) 具有偶数个0和奇数个1的有0和1组成的符号串的全体。

答：设S是符合要求的串，|S|=2k+1 (k≥0）。

则S→S10|S21，|S1|=2k (k>0），|S2|=2k (k≥0）。

且S1是{0,1}上的串，含有奇数个0和奇数个1。

S2是{0,1}上的串，含有偶数个0和偶数个1。

考虑有一个自动机M1接受S1，那么自动机M1如下：和L(M1)等价的正规表达式，即S1为：((00|11)|(01|10)(00|11)*(01|10))*(01|10)(00|11)*类似的考虑有一个自动机M2接受S2，那么自动机M2如下：和L(M2)等价的正规表达式，即S2为：((00|11)|(01|10)(00|11)*(01|10))*因此，S为：((00|11)|(01|10)(00|11)*(01|10))*(01|10)(00|11)*0|((00|11)|(01|10)(00|11)*(01|10))*1(6) 不包含子串011的由0和1组成的符号串的全体。

答：1*|1*0(0|10)*(1|ε)(7) 由0和1组成的符号串,把它看成二进制数，能被3整除的符号串的全体。

答：假设w的自动机如下：对应的正规表达式：(1(01*0)1|0)*2 给出接受下列在字母表{0,1}上的语言的DFA。

符号串的幂运算
符号串的幂运算是指将一个符号串自乘若干次，得到的新符号串。

例如，字符串“ab”自乘2次得到“abab”，自乘3次得到“ababab”。

在幂运算中，空串的幂为1。

符号串的幂运算在密码学中有广泛的应用。

例如，在RSA加密算法中，公钥和私钥的生成就涉及到符号串的幂运算。

符号串的幂运算可以通过循环或递归实现。

循环实现的代码比较简单，但递归实现的代码更加优美和简洁。

需要注意的是，符号串的幂运算可能会导致字符串长度过长，因此在实现时需要考虑空间复杂度。

- 1 -。

目标符号串生成速查表名称代码名称代码名称代码5月10日5，6，7，8，9，1011月15日11，12，13，14，1516-2016，17，18，19，2021-2521，22，23，24，2526-3026，27，28，29，30教室教室，音体美教室实验室实验室，运动场，电脑房图书室图书室，电子阅览室家庭自己家，朋友家，长辈家社区村组，小区，乡镇，县辖区纸笔A31纸笔仪器A32仪器电脑A33电脑互联网A34学习网学习机A35学习机文本A41教材，教辅，学案，题组声响A42演讲，录音，广播，音频图画A43图表，动画，录像、影视资源网A44校园网，人教网，电教网现实A45实物，林园，机构，景观识别B11回忆；再现，知道；辨认，说出；指出、区别、辨别；判断。

理解B12举例；列出；列举；排列；比较；分类；划分；归类；选出。

应用B13得出；联系；分析；归纳；总结；探讨；采用；使用；应用；利用。

感受B21注意；关心；关注；感触；感悟；经历；体验；反思。

认同B22认同；选择；拒绝；辩论；辩护；热爱；忠诚。

领会B23确立、形成、养成、决定、爱护，树立；选定；坚定；坚持。

观察B31听出；说出；阅读；浏览；精读；泛读；测定；观察；参观；参加；参与；搜索；查找；找出；收集；处理；提炼；访问。

表述B23写出；描绘；描述；概述；简述；仿写；仿作；概括；说明；解释；阐明；撰写；演讲；交流；演示；表演；竞赛。

操作B33模仿；仿效；尝试；探究；研究；探索；制作；测定；调查；实验；实习；实践。

课程基元目标要素符号生成速查表类属型有效资源习得动词B ij有效时间有效空间有效工具有效信源认知动词情感动词技能动词A3jA4jB1jB2j样B3j名称代码名称代码名称代码单词C11C;H;O;N;S;-NH2;-COOH;-R;氨基；羧基，氨基酸；…短语C12侧链R基团;氨基酸的分子结构式；氨基酸的通式；脱水缩合；二肽；散肽；多肽单句C13生物体内有氨基酸2种；氨基酸是构成蛋白质的单元。

字符串的概念
字符串是由字符组成的序列，可以包含字母、数字、符号和空格等字符。

在编程语言中，字符串通常被表示为一系列字符的集合，可以用引号或其他特定字符标记字符串的开始和结束。

字符串主要用于存储和操作文本数据，也可以表示更通用的数组或其他序列（或列表）数据类型和结构。

字符串在计算机内部通常以字符数组的形式存储，其中每个字符占据一定的内存空间。

字符可以是任何Unicode字符，包括ASCII字符和扩展字符。

字符串通常被认为是一种数据类型，用于表示和操作文本数据。

在程序设计中，字符串（或串）为符号或数值的一个连续序列，如符号串（一串字符）或二进制数字串（一串二进制数字）。

字符串的长度是指字符串中字符的数量，通常以字节或字符为单位进行度量。

字符串也可以包含子串，即字符串中的一段字符序列。

子串可以是字符串整体的一个子集，也可以是其他字符串中的一部分。

此外，字符串还可以进行模式匹配、查找、替换等操作。

总之，字符串是编程中常用的数据类型之一，用于表示和操作文本数据。

在实际应用中，根据具体的需求和场景，可以使用不同的编程语言和字符串处理方法来处理字符串数据。

第一章编译程序是一种程序,它把高级语言编写的源程序翻译成与之在逻辑上等价的机器语言或汇编语言的目标程序。

一个高级语言程序的执行通常分为两个阶段,即编译阶段和运行阶段。

如果编译生成的目标程序是汇编语言形式,那么在编译与运行阶段之间还要添加一个汇编阶段.解释程序也是一种翻译程序,它将源程序作为输入，一条语句一条语句地读入并解释执行。

解释程序与编译程序的主要区别是：编译程序是将源程序翻译成目标程序后再执行该目标程序,而解释程序则是逐条读出源程序中的语句并解释执行，即在解释程序的执行过程中并不产生目标程序。

编译过程源程序符串进行扫描和分解,个具有独立意义的单词；语法分析的任务的基础上,根据语言的语法规则(号串中识别出各种语法单位并进行语法检查；和中间代码生成阶段的任务来描述这种语义即生成中间代码；优化的任务高效（节省时间和空间）的目标代码；的任务定机器上的机器语言程序或汇编语言程序，实现最终的翻译工作。

自编译:用某种高级语言书写自己的编译程序。

交叉编译：指用A机器上的编译程序来产生可在B机器上运行的目标代码。

自展:首先确定一个非常简单的核心语言L0，然后用机器语言或汇编语言书写出它的编译程序T0：再把语言L0扩充到L1，此时有L0 L1，并用L0编写L1的编译程序T1(即自编译）。

移植：指A机器上的某种高级语言的编译程序稍加改动后能够在B机器上运行.第二章对程序设计语言的描述是从语法、语义和语用3个因素来考虑的。

所谓语法是对语言结构的定义;语义是描述了语言的含义；语用则是从使用的角度去描述语言。

形式化的方法:用一整套带有严格规定的符号体系来描述问题的方法。

标识符：以字母打头的字母数字串字母表：是元素的非空有穷集合。

字符：字母表中的元素称为符号，或称为字符。

可以是字母、数字和其他符号。

符号串：符号的有穷序列。

前缀:指从末尾删除0个或多个符号后得到的符号串.后缀：指从开头删除…。

（同上）符号串的运算:符号串的连接、集合的乘积、符号串的幂运算、集合的幂运算、集合A的正闭包A+与闭包A*形式语言：字母表上所有的字符按照某种规则所组成的集合。

编译原理什么是编译程序？编译程序也叫编译系统，是把用高级语言编写的面向过程的源程序翻译成目标程序的语言处理程序。

编译的各个阶段什么是文法？文法是以又穷的集合刻画无穷的集合的一个工具。

1、字母表:它是非空有穷集。

例如：∑={a,b,c}或∑={1,2,3}2、符号：字母表中的元素称为符号。

3、符号串：符号的有穷序列，符号串也称为字。

用ε来表示空符号串。

例如：a,ab,abc4、长度：符号串的长度是指该串所包含的符号个数。

用|x|表示符号串x的长度。

例如：|a|=1，|abn|=35、连结：设x和y为符号串，则称xy 为他们的连结。

例如：x=aa,y=bb,则xy=aabb6、空集：不含任何元素的集合,记为 。

7、乘积：设A和B是符号串集，则用AB表示A和B的乘积。

A={a,b},B={c,d},则AB={ac,ad,bc,bd}8、方幂：设A为符号串集，则定义A0={ε}A1=AA n=A n-1 A例如：A={a,b} 则有：A0={ε} A1={a,b}A2={aa,ab,ba,bb}9、正闭包：设A为符号串集，则用A+表示A的正闭包，其具体定义如下：A+=A1∪A2∪A3∪⋯…例如：A={a},A+={a,aa,aaa,……}10、星闭包：设A为一集合，则定义A的星闭包为A* ，其具体定义如下A*=A0∪A+例如：A={a},A*={ε,a,aa,aaa,……}文法G定义为四元组(V N，V T，P，S )其中V N为非终结符号(或语法实体，或变量)集；V T为终结符号集；P为产生式(也称规则)的集合；V N，V T和P是非空有穷集。

S称作识别符号或开始符号，它是一个非终结符，至少要在一条产生式中作为左部出现。

V N和V T不含公共的元素，即V N∩V T = φ用V表示V N ∪V T，称为文法G的字母表或字汇表例文法G=（V N，V T，P，S）V N = { S }, V T ={ 0, 1 }P={ S→0S1, S→01 }S为开始符号推导：用若干次产生式可从x串导出y串，则称y为x的推导，记为x y。