精华内容
下载资源
问答
  • 蒋宗礼形式语言自动机课后答案,答案是前四章,网上至今没有流出五章之后的答案,希望有能人志士可以补充后面的答案
  • 形式语言与自动机理论-peter linz 第三版中文版.形式语言与自动机理论-peter linz 第三版中文版.形式语言与自动机理论-peter linz 第三版中文版.
  • 形式语言与自动机理论,清华大学出版社蒋宗礼版教材对应的课件
  • 形式语言与自动机理论(第2版) 蒋宗礼 课后答案[1-12章].pdf
  • 网络下载,回归网络,《形式语言与自动机理论》习题答案
  • 北邮 形式语言与自动机

    千次阅读 多人点赞 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章部分课后题答案。
  • 形式语言简介

    千次阅读 2018-07-06 10:14:14
    说句大实话,基于极限论的菲氏微积分不需要形式语言的帮助,与此相反,基于模型论的无穷小微积分却离不开形式语言的支撑。 那么,形式语言是什么呢?在数学、逻辑(包括模型论)和计算机科学中,形式语言(Formal ...

    当前,我国普通高校微积分教育改革正好处在一个十字路口。是前进,还是后退?

    说句大实话,基于极限论的菲氏微积分不需要形式语言的帮助,与此相反,基于模型论的无穷小微积分却离不开形式语言的支撑。

    那么,形式语言是什么呢?在数学、逻辑(包括模型论)和计算机科学中,形式语言(Formal language)是用精确的数学或机器可处理的公式定义的语言语言。形式语言一般有两个方面: 语法和语义。专门研究语言的语法的数学和计算机科学分支叫做形式语言理论,它只研究语言的语法而不致力于它的语义。在形式语言理论中,形式语言是一个字母表上的某些有限长字符串的集合。一个形式语言可以包含无限多个字符串。

    大家知道,形式语言可以套用在菲氏上,但是,菲氏偏偏么不用。塔尔斯基创立的数学模型论,利用形式语言精确地描述微积分理论,1960年,鲁宾逊发现微积分学存在超实数模型,据此Keisler把微积分学的形式语言描述的景象,创造性地利用理想显微镜与望远镜重新恢复了莱布尼兹的微积分。

    事情很简单,就是这么回事情,反对无穷小微积分是短视。

    袁萌 7月7日

    展开全文
  • 哈工大2020春形式语言与自动机期末试题
    展开全文
  • 形式语言与自动机

    千次阅读 2017-07-11 22:51:40
    形式语言1.形式语法定义无论哪种语言都是句子和符号串的集合,描述一种语言的三种方法: 1. 穷举法:把语言中的所有句子都枚举出来。 2. 文法描述:语言中的每个句子用严格定义的规则来构造,利用规则生成语言中...

    形式语言

    1.形式语法定义

    无论哪种语言都是句子和符号串的集合,描述一种语言的三种方法:
    1. 穷举法:把语言中的所有句子都枚举出来。
    2. 文法描述:语言中的每个句子用严格定义的规则来构造,利用规则生成语言中合法的句子。(用来精确地描述语言和其结构)
    3. 自动机法:通过对输入的句子进行合法性检验,区别哪些是语言中的句子,哪些不是。(用来机械地刻画对输入字符串的识别过程)

    定义(形式语法):一个四元组G=(N,∑,P,S),其中N是非终结符的有限集合;∑是终结符号的有限集合,N∩∑=∅;V=N∪∑称为总词汇表;P是一组重写规则的有限集合:P={α->β},其中α,β是由V中元素构成的串,但是α中至少应含有一组非终结符号;S∈N称为句子符或初始符。


    附录【字符串的闭包运算】字符表∑上的符号串集合V的闭包定义为:V*=V0∪V1∪V2∪….,V+=V1∪V2∪….(或 V*-{ε})。
    e.g.: V={a,b},则 V*={ ε,a,b,aa,ab,bb,ba,aaa,…} V+={a,b,aa,ab,bb,ba,aaa,…}


    定义(推导):设G=(N,∑,P,S)是一个文法,在(N∪∑)*上定义关系 =G=> 为:
    如果αβγ是 (N∪∑)*中的字符串,且β->δ是P中的一个产生式,那么αβγ =G=> αδγ。

    按非平凡方式派生 =G+=>:表示=G=>的传递闭包,即(N∪∑)*上的符号串ξi到ξi+1(i>=0)至少经过一步推导或派生。
    派生=G*=>:表示=G=>的自反或传递闭包,即由(N∪∑)*上的符号串ξi到ξi+1经过n(n>=0)步推导或派生。
    这里写图片描述
    【其中最右推导为规范推导】

    定义(句子)文法G=(N,∑,P,S)的句子形式通过如下递归方式定义:1)S是一个句子形式;2)如果γβα是一个句子形式,且β->δ是P中的产生式,那么γδα也是一个句子形式。
    对于文法G,不含非终结符的句子形式成为G生成的句子。由文法G生成的语言(或称G识别的语言)是指G生成的所有句子集合,记作 L(G)={x|x∈∑,S=G*=>x}。

    2.形式语法的类型

    正则文法(3型文法)

    定义(正则文法):如果文法G的规则集P中所有规则均满足如下形式:A->Bx,或A->x,其中A,B∈N,x∈∑,则称该文法G为正则文法。

    A->Bx为左线性正则文法
    A->xB为右线性正则文法

    这里写图片描述

    上下文无关文法(2型文法)

    定义(上下文无关文法):如果文法G的规则集P中所有规则均满足如下形式:A->α,其中A∈N,α∈(N∪∑)*,则称文法G为上下文无关文法(CFG,context-free grammar)。
    这里写图片描述

    上下文有关文法(1型文法)

    定义(上下文有关文法):如果文法G的规则集P中所有规则满足如下形式:αAβ->αγβ,其中A∈N,α,β,γ∈(N∪∑)*,且γ至少包含一个字符,则称文法G为上下文有关文法(CSG,context-sensitive grammar)。
    从定义可以看出,字符串αAβ中的A被改写成γ时需要有上文语境α和下文语境β。当α和β为空字符 ε时,1型文法变成了2型文法,即2型文法是1型文法的特例。
    这里写图片描述
    通过这个例子看出,规则左部不一定仅为一个非终结符,可以有上下文限制,但规则右端的长度不小于规则左部的长度。
    因此该文法另一种定义:如果文法G为上下文有关文法,当且仅当x->y,x∈(N∪∑)+,y∈(N∪∑)*,并且|y|>=|x|。

    无约束文法(0型文法)

    定义(无约束文法):如果文法G的规则集P中所有规则满足如下形式:α->β,其中α∈(N∪∑)+,β∈(N∪∑)*,则称G为无约束文法或无限制重写系统。
    这里写图片描述

    3.CFG识别句子的派生树表示

    一个上下文无关文法G=(N,∑,P,S)产生句子的过程可以由派生树(语法树/分析树/推导树)表示。
    派生树构造步骤:
    这里写图片描述
    定义(二义性文法):如果文法G对于同一个句子存在两棵或者两棵以上不同的分析树,那么该句子是二义性的,文法G为二义性文法。
    这里写图片描述
    这里写图片描述

    自动机理论

    有限自动机(FA,finite automatic)

    1.确定性有限自动机(DFA,definite automata)

    定义(确定性有限自动机)DFA M是一个五元组:M=(∑,Q,δ,q0,F)。其中∑是输入符号的有穷集合;Q是状态的有限集合;q0∈Q是初始状态;F⊆Q是终止状态集合;δ是Q与∑的直积Q×∑到Q(下一个状态)的映射,它支配着有限状态控制的行为,有时也称为状态转移函数。
    这里写图片描述
    原理:处在状态q∈Q中的有限控制器从左到右依次从输入带上读入字符。开始时有限控制器处在状态q0,输入头指向∑*中一个链的最左符号。映射δ(q,a)=q’ (q,q’∈Q,a∈∑)表示在状态q时,若输入符号为a,则自动机M进入状态q’并且将输入头向右移动一个字符。
    定义(DFA接受的语言)如果一个句子x对于有限自动机M有δ(q0,x)=p,p∈F,则称句子x被M接受。被M接受的句子的全集称为由M定义的语言,或称M所接受的语言,记作T(M)={x | δ(q0,x)∈F}。

    用状态图描述映射δ,δ(q,a)=q’的状态转换图如下:
    这里写图片描述

    状态转换图的构造方法:每个状态作为一个节点,用圆圈表示。如果处在状态q并接受输入符号a∈∑时的DFA转移到q’状态,那么画一条有向弧从状态q到达状态q’,标记为a。终止状态用双圈表示,开始状态用带“开始”说明的箭头标出。
    这里写图片描述
    该DFA识别的语言为“所有0、1构成的至少包含一个0的字符串”。

    2.不确定性有限自动机(NFA,non-definite automata)

    定义(不确定的有限自动机)NFA M是一个五元组:M=(∑,Q,δ,q0,F)。其中∑是输入符号的有穷集合;Q是状态的有限集合;q0∈Q是初始状态;F是终止状态集合,F⊆Q;δ是Q与∑的直积Q×∑到Q的幂集2Q的映射。

    NFA与DFA的重要区别是:在NFA中δ(q,a)是一个状态集合,而在DFA中δ(q,a)是一个状态。根据定义,对于NFA M有映射:δ(q,a)={q1,q2,…,qk},k>=1。
    即NFA M在状态q时,接受输入符号a时,M可以选择状态集q1,q2,…,qk中任何一个状态作为下一个状态,并将输入头向右边移动一个字符的位置。

    定义(NFA接受的语言)如果存在一个状态p,有p∈δ(q0,x)且p∈F,则称句子x被NFA M所接受。被NFA M接受的所有句子的集合称为NFA M定义的语言,记作T(M)={x | p∈δ(q0,x) 且 p∈F}。

    定理:设L是被NFA所接受的语言,则存在一个DFA,它能够接受L。

    3.正则文法与自动机的关系

    重要结论:对于任意一个正则文法所产生的语言,总可以构造一个确定的有限自动机识别它。(即对任意一个正则文法,总可以构造一个确定的有限自动机)
    两个定理
    G->FA
    这里写图片描述
    FA->G
    这里写图片描述
    e.g.:
    这里写图片描述
    这里写图片描述

    下推自动机(PDA,push-down automata)

    下推自动机(PDA)可以看成是一个带有附加下推存储器的有限自动机,下推存储器是一个堆栈(stack)。原理示意图如下:
    这里写图片描述
    定义(PDA)不确定的下推自动机可以表达成一个七元组:M=(∑,Q,τ,δ,q0,Z0,F)。其中∑是输入符号的有穷集合;Q是状态的有限集合;τ为下推存储器符号的有穷集合;q0∈Q是初始状态;Z0∈τ为最初出现在下推存储器顶端的开始符号;F⊆Q是终止状态集合;δ是从Q×(∑∪{ ε})×τ到Q×τ*的子集的映射。

    这里写图片描述

    图灵机(Turing machine)

    图灵机VS有限自动机, 图灵机可以通过其读写头改变输入带上的字符。

    定义(图灵机)一个图灵机T可以表达成一个六元组:T=(∑,Q,τ,δ,q0,F)。其中∑是输入/输出带上字符的有穷集合,不包含空白符号B;Q是状态的有限集合;τ是输入符号的有穷集合,包含空的符号B,∑⊆τ,τ=∑∪{B};q0∈Q是初始状态;F⊆Q是终止状态集合;δ是从Q×τ到Q×(τ-{B})×{R,L,S}子集的一个映射。其中R,L,S分别表示右移一格,左移一格和停止不动。
    这里写图片描述

    线性界限自动机(linear-bound automata)

    线性界线自动机是一个确定的单带图灵机,其读/写头不能超越原输入带上字符串的初始和终止位置,即线性界线自动机的存储空间被输入符号串的长度所限制。

    定义(线性界线自动机)一个线性界线自动机M可以表达成一个六元组:M=(∑,Q,τ,δ,q0,F)。其中τ是输入/输出带上符号的有穷集合;Q是状态的有限集合;∑是输入/输出带上字符的又穷集合,∑⊆τ;q0∈Q是初始状态;F是终止状态集合,F⊆Q;δ是从Q×τ到Q×τ×{R,L}子集的映射。
    ∑包括两个特殊符号#和$,分别表示输入链的左端和右端结束标志。
    这里写图片描述
    这里写图片描述

    总结

    各类自动机之间的主要区别是它们能够使用的信息存储空间的差异:
    1. 有限状态自动机只能用状态来存储信息
    2. 下推自动机除了使用状态以外,还可以用下推存储器(堆栈)
    3. 图灵机等价于无约束文法
    4. 线性界线自动机可以利用状态和输入/输出带本身,因为输入/输出带没有“先进后出”的限制

    展开全文
  • 形式语言与自动机 答案 北邮 王柏

    热门讨论 2008-11-13 13:35:08
    北京邮电大学形式语言与自动机王柏第四,五章课后题答案
  • 哈尔滨工业大学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...
  • 摘要: 形式语言与自动机是计算机科学的理论基础,对于计算机科学与技术专业人才的计算思维能力培养极其重要。本文首先从Chomsky谱系出发,对形式语言的概念和类别进行了阐述,然后按照形式文法与自动机之间的对应...
  • 形式语言自动机教学参考书.pdf

    热门讨论 2012-11-04 21:43:52
    形式语言与自动机理论教学参考书(蒋宗礼 ,清华大学出版社)高清pdf版,另外我还把搜集的前四章的详细答案一并打包。形式语言有这些就足够了。
  • 形式语言与自动机 第三章 课后题答案

    千次阅读 多人点赞 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},{...
  • 考点:图灵机⇒语言 解:工作过程:首先从 q0q_0q0​ 将读入的0改为1,读头向右移动到状态 q1q_1q1​,然后;读入1则改为0读头向右移动回到状态 q0q_0q0​,若读入B则不变,读头向右移动到状态 qfq_fqf​ 接收的语言...
  • 哈工大形式语言与自动机历年试题

    热门讨论 2012-11-05 18:48:12
    哈工大形式语言与自动机历年试题,含答案的哦,仅供参考
  • 形式语言与自动机学习心得

    千次阅读 2017-01-01 16:32:46
    教材《形式语言与自动机》朱保平 李千目编著 清华大学出版社   说明:本文尽可能避免使用繁琐的数学表达,和只求信不求达雅的文字定义。无法避免时用注释方式给出   一、形式语言和自动机的关系 形式语言和...
  • P37 4、6、7课后题答案
  • 数学的符号语言与形式语言

    千次阅读 2017-06-25 09:06:07
    形式语言和自然语言本质上都是一种符号系统,形式语言是人为的设计的,而自然语言则是在人类进化过程中自然演化的。自然语言的发展是先出现语音的区别来表意,接着出现文字,而数字的出现则要晚很多。数字的出现则是...
  • 形式语言——四类文法

    千次阅读 2016-06-20 16:20:38
    参考:形式语言文法定义G=(N,∑,P,S),其中N为终止符集合,∑为终止符集合,P为产生式集合,S为起始语句G=(N,\sum,P,S),其中N为终止符集合,\sum 为终止符集合,P为产生式集合,S为起始语句 0-型文法(无限制文法或...
  • 如自然语言理解(一)中介绍的,我们把将一个句子映射到它的逻辑形式这个过程称为语义理解(semantic interpretation)。 为什么我们需要语言的逻辑形式呢?这是因为同样的一句话,在不同的语境(上下文)下可以...
  • 自然语言(Natural Language)就是人类讲的语言,比如汉语、英语和法语。...形式语言(Formal Language)是为了特定应用而人为设计的语言。例如数学家用的数字和运算符号、化学家用的分子式等。
  • 形式语言与自动机理论总结

    万次阅读 多人点赞 2012-06-17 10:54:34
     2)正则语言的乘积(连接)是正则语言。  3)正则语言的差是正则语言。  4)正则语言的闭包是正则语言。  5)正则语言的商是正则语言。  6)正则语言的同态是正则语言。  7)正则语言的逆转是...
  • 接受语言 L={w2w T | w ∈ {0,1} * } 的 PDA 的设计。 先设计产生 L 的 CFG G 1 : G 1 : S ® 2|0S0|1S1 再将此文法转化成 GNF : G 2 : S ® 2|0SA|1SB A ® 0 B ® 1 句子 0102010...
  • 形式语言的重要性

    千次阅读 2019-02-26 23:16:59
    2.半形式化的语言(数学语言),即自然语言加特定的符号。 3.形式化的语言(逻辑语言) 半形式语言 任何一个数学分支的语言都是在自然语言的基础上附加一些特定的符号,它们与自然语言相比更具形式化。因此,称它...
  • 文法G=(V,T,P,S) G叫做0型文法(type 0 grammar)...也可以叫做短语结构语言(PSL)、递归可枚举集(recursively enumerable ,r.e. )。 对应的其识别语言机器为图灵机(TM:turing machine) G是0型文法。   如果对
  • 编译原理第二章上下文无关文法和形式语言课后题

    千次阅读 多人点赞 2019-03-17 11:21:55
    A 一一对应,一个文法对应唯一的语言,并且,一个语言对应唯一的文法 B 一个语言对应唯一的文法,反之则不然 C 一个文法对应唯一的语言,反之则不然 D 若为非二义文法,则C正确;若为二义文法,则一个文法...
  • 一种形式化描述语言,用于建模!是一种基于数学的形式化描述语言
  • 文章目录高级语宫及其语法描述(一)程序语言的定义(二)高级语言的一般特性1、高级语言的分类2、数据类型与操作 高级语宫及其语法描述 ...定义语言的词法和语法的形式规则; 语义:是描述语言的含义;定义语言...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,025,580
精华内容 410,232
关键字:

形式语言