-
2020-07-29 12:22:05更多相关内容
-
蒋宗礼《形式语言与自动机》课后答案
2018-12-15 16:36:38蒋宗礼形式语言自动机课后答案,答案是前四章,网上至今没有流出五章之后的答案,希望有能人志士可以补充后面的答案 -
形式语言与自动机理论-peter linz 第三版中文版.
2018-01-09 18:32:27形式语言与自动机理论-peter linz 第三版中文版.形式语言与自动机理论-peter linz 第三版中文版.形式语言与自动机理论-peter linz 第三版中文版. -
形式语言与自动机理论(第2版) 蒋宗礼 课后答案[1-12章].pdf
2019-07-21 21:57:26形式语言与自动机理论(第2版) 蒋宗礼 课后答案[1-12章].pdf -
自然语言和形式语言
2021-12-24 00:29:24二,形式语言 一,自然语言 1,自然语言的范畴 自然语言的范畴,主要包括读音、字形、含义三大类。 读音是耳朵相关,字形是眼睛相关,含义是大脑相关,这三者都互相相关,并不独立。 读音方面,主要是音节和...目录
一,自然语言
1,自然语言的范畴
自然语言的范畴,主要包括读音、字形、含义三大类。
读音是耳朵相关,字形是眼睛相关,含义是大脑相关,这三者都互相相关,并不独立。
读音方面,主要是音节和音调。
字形方面,主要是字母或者偏旁部首怎么组成单词。
含义方面,主要是包括语法、语义。
2,最小单元
简单的理解,英语最小单元是字母,大一点是词,再大一点是词组,再大一点是句子,汉语最小单元是字,大一点是词,再大一点是词组,再大一点是句子。
看起来还挺统一的,但从字形上,汉字还可以拆分,从发音上,一个汉字是一个独立的发声单元,而英语中字母却不是独立的发声单元,从含义上,单英文字母是没有含义的,汉字是有含义的,很多英语单词可以和汉字的含义对应,比如good好,look看。
(1)音节、读音
音节(Syllable)是语言中单个元音音素和辅音音素组合发音的最小语音单位,单个元音音素也可自成音节。
汉语的音节是由声母和韵母相拼组成的语音单位,单个韵母也可自成音节。
对英语西语俄语等非声调语言来说,其发音主体是音节。对汉语、泰语等声调语言来说,其语音除了音节还有声调,音节加上声调就是读音。(2)单字、单词
汉语的单词即汉字,一个汉字就是一个音节,汉字的字形由偏旁部首构成。
英语的单词就是单词,有单音节单词,也有多音节单词,单词由英文字母构成。
(3)语素
语素是指语言中最小的音义结合体。
对于单音节语,如汉语、越南语、泰语等,语素大部分都是单音节的。
对于其他语言,语素由一到多个音节组成。
- 汉语的单音节语素:天、地、人、跑、跳、唱、红、白
- 汉语的双音节语素:琵琶、乒乓、澎湃,其中单个的字没有含义
- 汉语的多音节语素:喜马拉雅、珠穆朗玛,其中的马作为单个的字倒是有含义,但是并没有组成喜马拉雅这个词的含义。
(4)词
词是构成句子的最小单位。
语素和词的含义很接近,词是一到多个语素组合而成。
比如,“春来了吗?”,春是语素,也是词。“春天来了吗?”春是语素,天是语素,春天是词。
3,语法、词法、句法
语法是从众多的语法单位里抽象出其中共同的组合方式、类型及如何表达语义的规则。
语法包括词法和句法。语法也叫文法。
词法,就是词的分类、性质、作用。词法也叫字法。
句法是词如何构成句子,即句子的分类和构成规则等。
语法有如下主要特点:
(1)抽象性
语法从词和句的个别和具体的东西中抽象出来,把作为词的变化和用词造句的基础一般的东西拿来,并且以此构成语法规则、语法规律。
例如汉语里有“看看、说说、写写、学习学习、讨论讨论”这一词的重叠现象,这反映出一条词的变化规律:有些动词可以用重叠的方法来表示动作的某一语义类型,即表示少量或短时。
语法学的任务是描写,解释组成词、短语和句子的规则和格式。由此可见,语法具有抽象性、概括性。
(2)生成性
我们可以根据有限的语法规则造出无数合格的句子来,这就表现了语法的生成性。语法规则的生成性,集中的表现在两个方面:组合关系和聚合关系。
组合关系指的是语序结构。比如我吃饭(S+V+O)。你看书。他写字。上述都是同一种组合关系。
聚合关系,你、我、他都是人称代词,是一种聚合关系。饭、书、字在上述例子中都做宾语(实体名词),也是一种聚合关系。(3)系统性
语法是一个严密的立体的开放的系统网络。
所谓“严密”,是指系统的内部是相互制约的,要受到一定的规则的支配,不是可以随心所欲的。
所谓“立体”,是指语法系统包括了句法结构,语法意义,语言运用这三个交叉的不同平面。
所谓“开放”,是指语法系统是发展变化的,一直在不断地自我完善,旧的成份被逐渐淘汰,新的因素在不断产生。
语法系统内部又由若干个子系统构成,例如语素系统,词类系统,短语系统,句子系统,句群系统,每个子系统可能由若干个孙系统构成。词类系统内部可以分为实词系统和虚词系统。句子系统内部可以分为单句系统,复句系统等等,从而形成一个系统网络。
(4)层次性
语法从表面上看是线性排列的东西,但是语法结构却是有层次性的。
语法的层次性与语法的递归性密切相关。
(5)递归性
递归是说,各种语法结构的关系是有限的,但是在语言单位的组合过程中,可以反复无限地使用这些有限的规则,从而使句法结构复杂化。例如:我买书。/我买一本书。/我买一本有趣的书。
4,语义
关于知识的概念没有明确的定义,一般来说,知识为人类提供了一种能够理解的模式用来判断事物到底表示什么或者事情将会如何发展。从知识的陈述特性上来看,知识即指用来描述信息的概念、概念之间的关系,以及概念在陈述具体事实时所必须遵守的条件。从这一点看,对于信息的语义以及信息语义之间的关联关系的描述本身就是一种知识的表达,因此在许多研究中,往往将语义的描述等同于知识的描述。
二,形式语言
1,形式语言
为了消除自然语言的多义性,我们发明并使用形式语言。形式语言是只注重形式而不注重内容,即只有语法而没有语义。
形式语言是一个字母表上的某些有限长字符串的集合。
数学家用的数字和运算符号、化学家用的分子式、程序员用的编程语言都是形式语言。
形式语言理论,只研究语言的语法而不致力于它的语义。
形式语言的语法,同样分为词法和句法。
2,最小单位——Token
形式语言的最小单位是Token
Token的概念相当于自然语言中的单词和标点、数学式中的数和运算符、化学分子式中的元素名和数字。
关于Token的规则就是词法,Token如何形成形式语法就是句法。
以编程语言为例:
int func();
int、func、(、)、; 共5个token
3,形式文法的组成
文法即语法,形式文法就是形式语言的语法。形式文法包括词法和句法。
一个形式文法G由四个部分组成,可记作G={VT, VN, S , P }
(1)VT
VT是终结符(terminal)构成的集合,终结符就是Token
(2)VN
VN是非终结符(nonterminal)构成的集合,非终结符是Token组合而成的,比如短语,句子。
VT和VN的交集是空集,并集是文法符号集。
符号串是由文法符号集的若干成员依次排列形成。
(3)S
S是开始符号(start symbol),是语法中最大的语法成分(相当于自然语言中的句子)
(4)P
P是生成式(production)构成的集合,描述怎么通过一个符号串得到另外一个符号串。
生成式的一般表示法: a -> b,读作“a定义为b”
例如,包含加法和乘法的表达式,可以表示成:
其中,id是标识符,E是表达式
生成式有四条,分别表达了:
- 表达式+表达式 是 表达式
- 表达式*表达式 是 表达式
- (表达式)是 表达式
- 标识符 是 表达式
4,形式文法的简写
在不引起歧义的情况下,只用生成式就可以用来表示整个文法。
生成式的简写:
(1)候选式合并
a->b1 a->b2 a->b3
可以合并简写成
a>b1 | b2 | b3
所以上面的文法可以简写成 E -> E+E | E*E | (E) | id
5,四种文法
(1)0型文法
0型文法也称短语文法、短语结构文法、无限制文法。
一般表示法:a -> b,其中符号串a至少需要包含1个非终结符。
能力相当于图灵机,或者说任何0型语言都是递归可枚举的。
(2)1型文法
1型文法也称上下文有关文法,其能力相当于线性界限自动机。
一般表示法:a1a2a3 -> a1ba3,其中符号串a2的长度不超过符号串b的长度
即a2定义为b是有上下文的限制的。
(3)2型文法
2型文法也称上下文无关文法,其能力相当于非确定的下推自动机。
一般表示法:A->b,其中A是某个非终结符。
例如,表示标识符的上下文无关文法:
(4)3型文法
3型文法由于等价于正规式,所以也称正规文法、正则文法
正则文法分为左线性文法、右线性文法。
左线性文法的一般表示法:A->Bw,或A->B,其中w是终结符号串
右线性文法的一般表示法:A->wB,或A->B
所以,正则文法的符号串最多只能包含1个非终结符,而且只能全部在最左边,或者全部在最右边。
例如,表示标识符的右线性文法:
不难发现,这个文法和上一节的表示标识符的上下文无关文法是等价的。
(5)四种文法的关系
0型文法包含1型文法,1型文法包含2型文法,2型文法包含3型文法。
-
《形式语言与自动机理论》习题答案
2010-12-27 20:59:28网络下载,回归网络,《形式语言与自动机理论》习题答案 -
北邮 形式语言与自动机
2020-06-29 11:37:08本文总结 BUPT 计算机学院《形式语言与自动机》的学习资料,希望能帮到学弟学妹,打好基础。 从名字也能知道,这门课就是学形式化语言及其对应的自动机。这门课相对简单,知识脉络十分清晰。总结一下就是很简单。 ...一、前言
本文总结北邮计算机学院《形式语言与自动机》的学习资料,希望能帮到学弟学妹,打好基础。
从名字也能知道,这门课就是学形式化语言及其对应的自动机。这门课相对简单,知识脉络十分清晰。总结一下就是很简单。
《形式语言与自动机》同《离散数学》的感觉其实比较像,不难,也不会花太多时间,学科结构清晰。
二、思维导图
以下是自己总结的 XMind 思维导图,可以帮助梳理知识脉络,需要自取
链接:https://pan.baidu.com/s/1h7TI9tWXqFKibtPS8urVdA
提取码:6ld7放张图:
三、课后题
这门课在网上的资源较少,少有学校开这门课,因此课后题显得尤为重要,考试基本就是你没做过的课后题原题及其变种。
因为教材使用的是北邮自己编的教材,没有制作标准答案,只有一些网上流传的答案,不过质量还可以,除了有点丑以外,答案基本正确,不过因为版本原因,出现很多缺题现象。这里提供自己总结的课后题答案:
形式语言与自动机 第二章 课后题答案
形式语言与自动机 第三章 课后题答案
形式语言与自动机 第四章 课后题答案
形式语言与自动机 第五章 课后题答案四、其他学习资料
其他学习资料有限,我自己找到最好的是机械工业出版社的《形式语言与自动机导论》,作者是 Peter Linz,直接去看中文版就好。里面的例题和课后题比课程要求的要高一些,不过可以拓宽思路,考试万一遇到新颖的题目不至于脑子一片空白。
期末时候可以把期中题做一下用来复习前 2 章。
五、关于考试
因为疫情,我们只有期末考试,期中考试不了解,不过期中测试题还是有点难度的。期末考试难度较低,拿高分很简单,但要注意细节(比如起始状态能不能直接到 F)。
考试主要内容为设计自动机、文法等,这门课的考查点都很简单。要说有难度的就是设计题,但是如果设计不出来文法,也可以直接设计自动机然后转文法,还有就是 CH4 的泵浦引理(CH3 的泵浦引理出题很简单),可以多看看课后题和《形式语言与自动机导论》的泵浦引理,记住一些常见的证明思路。
以上,祝大家取得满意的成绩!
-
形式语言与自动机答案
2009-06-06 10:52:03这是自动机理论、语言与计算导论(第二版)的2-7章部分课后题答案。 -
《形式语言与自动机》(王柏、杨娟编著)课后习题答案
2009-12-18 18:58:38《形式语言与自动机》(王柏、杨娟编著)课后习题答案 -
形式语言与自动机 答案 北邮 王柏
2008-11-13 13:35:08北京邮电大学形式语言与自动机王柏第四,五章课后题答案 -
哈尔滨工业大学2019年《形式语言与自动机》期末试题
2019-07-03 20:58:44哈尔滨工业大学2019年《形式语言与自动机》期末试题 Design a DFA for the language L = {w∈{0,1}* | w contains both 01 and 10 as substrings}. Design a NFA within four states for the language {a}*∪{ab...哈尔滨工业大学2019年《形式语言与自动机》期末试题
-
Design a DFA for the language L = {w∈{0,1}* | w contains both 01 and 10 as substrings}.
-
Design a NFA within four states for the language {a}*∪{ab}*.
-
Design regular expressions for language over Σ = {0,1}.
(1).All strings contain the substring 001.
(2).All strings expect the string 001. -
Prove that L = {0m1n | m/n is an integer} is not regular with pumping lemma.
-
Convert the following NFA into DFA with subset construction.
-
Give a context-free grammar for L = { aibjci+j|i,j>=0}
-
Let L be the language generated by the grammar G below
S->AB|BBB
A->Bb|ε
B->aB|A
(1).消除空产生式
(2).消除单元产生式
(3).转换到CNF -
Design a PDA for L = {w∈{a,b}*|w has more a’s than b’s}
-
Prove : for every context free language L, the language L’ = {0|w||w∈L} is also context free.
-
Design a Turing Machine that computes the following function f:0n->Binary(n)
Where integer n>=1 and binary(n) is the binary representation of n.
For example: f(03) = 11 f(05) = 101.
注:此题目为考试试卷实录,敬请放心食用。
-
-
哈工大形式语言与自动机历年试题
2012-11-05 18:48:12哈工大形式语言与自动机历年试题,含答案的哦,仅供参考 -
计算语言学之形式语言与自动机
2017-03-19 15:37:07语言的形式有是什么样子?怎么才能形式化语言以使得计算呢?自动机是什么东西,和图灵机有关系么?说了这么多有什么用呢?这一个个疑问,我们将会在接下来的讲解中,为大家一一介绍。 1. 语言 谈到语言,想必是... -
形式语言与自动机 第四章 课后题答案
2020-06-05 10:48:19形式语言与自动机 第四章 课后题答案 -
形式语言与自动机
2017-07-11 22:51:40形式语言1.形式语法定义无论哪种语言都是句子和符号串的集合,描述一种语言的三种方法: 1. 穷举法:把语言中的所有句子都枚举出来。 2. 文法描述:语言中的每个句子用严格定义的规则来构造,利用规则生成语言中... -
形式语言与自动机 第五章 课后题答案
2020-06-14 20:10:17考点:图灵机⇒语言 解:工作过程:首先从 q0q_0q0 将读入的0改为1,读头向右移动到状态 q1q_1q1,然后;读入1则改为0读头向右移动回到状态 q0q_0q0,若读入B则不变,读头向右移动到状态 qfq_fqf 接收的语言... -
形式语言与自动机 第三章 课后题答案
2020-06-04 21:06:41考点:语言⇒DFA(设计DFA) 解:(1)M=({q0,q1,q2,q3},{a,b},δ,q0,{q3})M=(\{q_0,q_1,q_2,q_3\},\{a,b\},δ,q_0,\{q_3\})M=({q0,q1,q2,q3},{a,b},δ,q0,{q3}),其中 δ 如下: (2)M=({q0,q1,q2},{... -
形式语言自动机教学参考书.pdf
2012-11-04 21:43:52形式语言与自动机理论教学参考书(蒋宗礼 ,清华大学出版社)高清pdf版,另外我还把搜集的前四章的详细答案一并打包。形式语言有这些就足够了。 -
形式语言与自动机学习心得
2017-01-01 16:32:46教材《形式语言与自动机》朱保平 李千目编著 清华大学出版社 说明:本文尽可能避免使用繁琐的数学表达,和只求信不求达雅的文字定义。无法避免时用注释方式给出 一、形式语言和自动机的关系 形式语言和... -
形式语言与自动机及其在NLP中的应用
2018-04-28 14:56:41摘要: 形式语言与自动机是计算机科学的理论基础,对于计算机科学与技术专业人才的计算思维能力培养极其重要。本文首先从Chomsky谱系出发,对形式语言的概念和类别进行了阐述,然后按照形式文法与自动机之间的对应... -
形式语言与自动机 第二章 课后题答案
2020-06-04 18:10:58P37 4、6、7课后题答案 -
形式语言简介
2018-07-06 10:14:14说句大实话,基于极限论的菲氏微积分不需要形式语言的帮助,与此相反,基于模型论的无穷小微积分却离不开形式语言的支撑。 那么,形式语言是什么呢?在数学、逻辑(包括模型论)和计算机科学中,形式语言(Formal ... -
数学的符号语言与形式语言
2017-06-25 09:06:07形式语言和自然语言本质上都是一种符号系统,形式语言是人为的设计的,而自然语言则是在人类进化过程中自然演化的。自然语言的发展是先出现语音的区别来表意,接着出现文字,而数字的出现则要晚很多。数字的出现则是... -
形式语言与自动机理论总结
2012-06-17 10:54:342)正则语言的乘积(连接)是正则语言。 3)正则语言的差是正则语言。 4)正则语言的闭包是正则语言。 5)正则语言的商是正则语言。 6)正则语言的同态是正则语言。 7)正则语言的逆转是... -
需求分析——形式化语言和自然语言的区别
2019-05-28 15:42:32需求分析学习指导目录:... (1)形式化语言 用户容易理解 描述复杂 不同人理解容易产生歧义 (2)形式化语言(逻辑描述、集合描述、代数描述) 理解困难 表达准确 不会产生歧义 ... -
形式化语言的重要性
2019-02-26 23:16:59任何一个数学分支的语言都是在自然语言的基础上附加一些特定的符号,它们与自然语言相比更具形式化。因此,称它为半形式化的语言。 数学语言作为一种特定的符号语言,与自然语言相比,它与算法建立了联系。因此,它... -
形式化z语言辅助工具Z-EVES
2008-11-26 10:50:27形式化z语言辅助工具Z-EVES 进行形式化验证用 -
形式语言——四类文法
2016-06-20 16:20:38参考:形式语言文法定义G=(N,∑,P,S),其中N为终止符集合,∑为终止符集合,P为产生式集合,S为起始语句G=(N,\sum,P,S),其中N为终止符集合,\sum 为终止符集合,P为产生式集合,S为起始语句 0-型文法(无限制文法或... -
幼儿园语言活动形式有哪些
2020-12-21 13:10:07幼儿的语言能力是在运用过程中发展起来的,发展幼儿语言的关键是,创造一个能使幼儿想...那么,幼儿园语言活动形式有哪些呢?@视觉中国可以把幼儿园的语言教育,大体分为专门的语言教育活动和渗透性的语言教育活动两... -
人类语言的表现形式和规则
2020-03-14 08:45:52人类的于然善于描述什么那么使用这类人就可以快速的发展什么 例如中文艺术性强,所以中国书法...制作一个语言,就要有语言解释器 对于目前的人工智能的自动编码解码模式是十分相似的, 但是,机器怎么会比人类更厉害...