精华内容
下载资源
问答
  • 形式语言与自动机习题
    千次阅读 多人点赞
    2020-07-29 12:22:05

    更多相关内容
  • 形式语言与自动机 练习题总结

    千次阅读 2019-06-25 23:10:42
    {0,1}的子串全部串有:0,1,01,故本有三种状态 未发现 01, 即 0 没有出现过; 未发现 01, 但刚刚读入字符是 0; 已经发现了 01. 因此 DFA A 可定义为:A = ({q1,q2,q3},{0,1},δ,q1,{q3}) 其中 δ 为: δ...

    例2
    请设计 DFA, 在任何由 0 和 1 构成的串中, 接受含有 01 子串的全部串

    {0,1}的子串全部串有:0,1,01,故本题有三种状态

    1. 未发现 01, 即 0 没有出现过;
    2. 未发现 01, 但刚刚读入字符是 0;
    3. 已经发现了 01.
      因此 DFA A 可定义为:A = ({q1,q2,q3},{0,1},δ,q1,{q3})
      其中 δ 为:
      δ(q1,1) = q1 δ(q2,1) = q3 δ(q3,1) = q3
      δ(q1,0) = q2 δ(q2,0) = q2 δ(q3,0) = q3

    将此DFA用状态转移图表示:其中q1为初始状态
    在这里插入图片描述
    将此DFA用状态转移表表示:
    在这里插入图片描述
    求解接受全部含有 01 子串的 DFA, ˆ δ 处理串 0101 的过程
    解题过程借助如上的状态转移图
    在这里插入图片描述
    注意:ˆ δ(q0,ε) = δ(q0,0)

    例3.
    若 Σ = {0,1}, 给出接受全部含有奇数个 1 的串 DFA

    状态有两个:q0→偶数个1,q1→奇数个1,其中q1为接受状态
    在这里插入图片描述

    例4.
    若 Σ = {0,1}, 给出接受全部含有偶数个 0 和偶数个 1 的串 DFA

    接受状态:00,11,1100,111100,…
    在这里插入图片描述
    例5.
    对任何状态 q 及字符串 x 和 y, 证明 ˆ δ(q,xy) = ˆ δ(ˆ δ(q,x),y)

    @注意,类似此类证明,均对y进行数学归纳法
    1.y = ε 时,i
    在这里插入图片描述
    例7.
    由 0 和 1 构成的串中, 接受全部以 01 结尾的串, 如何设计 DFA?

    q0: XX11
    q1:XXX0
    q2:XX01
    在这里插入图片描述
    在这里插入图片描述
    续例7. 接受全部以 01 结尾的串的 NFA.
    在这里插入图片描述
    五元组为 A = ({q0,q1,q2},{0,1},δ,q0,{q2}),
    转移函数 δ:
    δ(q0,0) = {q0,q1} δ(q1,0) = ∅ δ(q2,0) = ∅
    δ(q0,1) = {q0} δ(q1,1) = {q2} δ(q2,1) = ∅

    续例7.
    接受 01 结尾的串的 NFA, ˆ δ 处理 00101 时每步的状态转

    在这里插入图片描述

    1. ˆ δ(q0,ε)={q0}
    2. ˆ δ(q0,0) = δ(q0,0) = {q0,q1}
    3. ˆ δ(q0,00) = δ(q0,0)∪δ(q1,0) = {q0,q1}∪∅ = {q0,q1}
    4. ˆ δ(q0,001) = δ(q0,1)∪δ(q1,1) = {q0}∪{q2} = {q0,q2}
    5. ˆ δ(q0,0010) = δ(q0,0)∪δ(q2,0) = {q0,q1}∪∅ = {q0,q1}
    6. ˆ δ(q0,00101) = δ(q0,1)∪δ(q1,1) = {q0}∪{q2} = {q0,q2}

    因为 q2 是接受状态, 所以 NFA 接受 00101

    例8.
    设计 L = {w ∈{0,1}∗ | w 的首尾字符相同.} 的 NFA

    续例11.
    L = {w ∈{0,1}∗ | w 倒数 3 个字符至少有一个是 1} 的 NFA.

    在这里插入图片描述
    例4.
    在这里插入图片描述
    例5.
    给出正则表达式 (aa)∗(bb)∗b 定义的语言

    在这里插入图片描述
    例6.
    Design regular expression for L = {w | w consists of 0’s and 1’s, and the third symbol from the right end is 1.}

    (0+1)∗1(0+1)(0+1)

    例7.
    Design regular expression for L = {w | w ∈{0,1}∗ and w has no pair of consecutive 0’s.}

    在这里插入图片描述

    例9.
    将如图 DFA 转换为正则表达式.

    在这里插入图片描述
    在这里插入图片描述
    例10.
    利用状态消除法, 设计下图自动机的正则表达式.

    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    例11.
    正则表达式 (0+1)∗1(0+1) 构造为 ε-NFA

    在这里插入图片描述
    例12. 判断 (L + M)∗ = (L∗M∗)∗.

    1. 将 L 和 M 替换为 a 和 b;
    2. (a+b)∗ ?= (a∗b∗)∗;
    3. 因为 L((a+b)∗) = L((a∗b∗)∗);
    4. 所以 (L + M)∗ = (L∗M∗)∗.

    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    例16.
    若语言 L = (00+1)∗, 同态 h : {a,b}→{0,1}∗
    为h(a) = 01, h(b) = 10,
    请证明 h−1(L) = (ba)∗

    1. 若w以a开头,则h(w) starts with 01,h(w) not in L;
    2. if w ends with b, then h(w) end with 10, h(w) not in L;
    3. if w contains consecutive aa, then h(w) contains 0101, h(w) not in L;
    4. if w contains consecutive bb, then h(w) contains 1010, h(w) not in L;
      So, h-1(L)=(ba)*

    例17.
    For a language L, define head(L) to be the set of all prefixes of strings in L. Prove that if L is regular, so is head(L)

    在这里插入图片描述

    展开全文
  • 蒋宗礼形式语言自动机课后答案,答案是前四章,网上至今没有流出五章之后的答案,希望有能人志士可以补充后面的答案
  • 形式语言与自动机理论试题答案解析.doc
  • 新版形式语言与自动机第二三章的答案,是北邮版的教材。
  • 形式语言与自动机理论(第2版) 蒋宗礼 课后答案[1-12章].pdf
  • 形式语言与自动机第二章答案~~~~~~~~~~~~~~~~~~~~~~~~~~
  • 形式语言与自动机理论--第五章(蒋宗礼PPT学习教案.pptx
  • bupt形式语言与自动机作业答案
  • 形式语言与自动机.rar

    2019-08-20 13:33:19
    本书采用通俗的语言和形象化的方法来表达概念和定理,逻辑严谨、思维缜密,可作为高等院校计算机及相关专业“形式语言与自动机”课程的教材。 [1] 作者简介编辑 陈有祺,南开大学信息技术科学学院教授,多年来一直...
  • 形式语言与自动机课后习题答案 第二章 偶 a 偶 b a 奇 a 偶 b 4 找出右线性文法能构成长度为 1 至 5 个字符且以字母为首的字符串 a 答 G={N,T,P,S} 其中 N={S,A,B,C,D} T={x,y} 其中 x {所有字母 } y {所有的字符 } ...
  • 北邮形式语言与自动机四五章课后习题答案
  • 形式语言与自动机课后习题答案 第二章 4 找出右线性文法能构成长度为1 至 5 个字符且以字母为首的字符串 答G={N,T,P,S} 其中 N={S,A,B,C,D} T={x,y} 其中 x {所有字母} y {所有的字符} P 如下: Sx SxA Ay AyB By ByC...
  • 网络下载,回归网络,《形式语言与自动机理论》习题答案
  • NLP学习笔记(3)——形式语言与自动机1.形式语言(1)语言(2)形式语言 1.形式语言 (1)语言 语言可以了解为一个抽象的数学系统,是按照一定的规律构成的句子和符号串的有限或无限的集合 ==语言描述的三种途径 =...

    1.形式语言

    (1)语言

    • 语言可以了解为一个抽象的数学系统,是按照一定的规律构成的句子和符号串的有限或无限的集合
    • ==语言描述的三种途径 ==
      (1)穷举法:只适合句子数目有限的语言
      (2)语法描述:生成语言中合格的句子
      (3)自动机:对输入的句子进行检验,区别哪些是语言中的句子,哪些不是语言中的句子

    (2)形式语言

    形式语言

    • 直观意义(定义):形式语言是用来精确地描述语言(包括人工语言和自然语言)及其结构的手段。
    • 形式语言学,也称为代数语言学。
    • 形式语言以重写规则 α→β的形式表示,其中α与β均为字符串。一个初步的字符串通过不同的顺序,不断应用不同的重写规则,可以得到不同的新字符串。

    形式语法

    形式语法是一个4元组G=(N,sigma,P,S)。
    其中N为非终结符的有限集合,或者说叫做变量集或语法种类集;
    sigma是终结符的有限集合,且有N∩sigma=∅;
    V=N∪sigma称为总词汇表;
    P是一组重写规则的有限集合:P={α→β},其中均为V中元素构成的字符串,且α中至少应该含有一个非终结符号;
    S∈N,称为句子符或者初始符。

    举个栗子:
    在这里插入图片描述

    关于推导

    (1)推导的定义
    在这里插入图片描述
    传递闭包:
    在这里插入图片描述
    自反和传递闭包:
    在这里插入图片描述
    当确定或者默认某个推导是由文法G所产生的,则推导符号下方的G可以省略不写。

    (2)最左推导、最右(规范)推导
    最左推导:约定每步推导中只改写最左边的那个非终结符。
    最右推导(规范推导):约定每步推导只改写最右边的那个非终结符。

    一个栗子:
    在这里插入图片描述
    (3)关于句型与句子

    文法G的不含非终结符的句子形式成为G生成的句子
    由文法G生成的语言,记做L(G),指G生成的所有句子的集合,即有
    L ( G ) = { x ∣ x ∈ ∑ , S ⇒ ∗ x } L(G)=\{x|x\in \sum,S \overset{*}\Rightarrow x \} LG={xx,Sx}

    (4)关于正则文法(3型文法)
    左线性正则文法称为3型文法
    关于正则文法,如果文法G=(N,sigma,P,S)的P,其中的规则满足如下的形式:A→Bx,或A→x,其中A,B∈N,x∈sigma,则称该文法为正则文法或3型文法(左线性正则文法);
    满足A→xB,则称该文法为右线性正则文法。

    (5)上下文无关文法(2型文法)——上下文有关文法的特例
    context-free grammar(CFG)
    如果P中的规则满足如下形式:A→α,其中A属于N,α属于(N∪sigma)*,则称该文法为上下文无关文法,或称2型文法。

    一个栗子:
    在这里插入图片描述
    (6)上下文有关文法(1型文法)
    context-sensitive grammar,CSG
    如果P中的规则满足如下形式:αAβ→αγβ,其中A∈N,α,β,γ∈(N∪sigma)*,且γ中至少包含一个字符(A直接消去的情况不予记录),则称该文法为上下文有关文法,或1型文法。

    当α和β均为空时,上下文有关文法转化为上下文无关文法,无关文法是有关文法的特例。

    或者定义为如下形式:
    在这里插入图片描述
    一个栗子:
    在这里插入图片描述
    (7)无约束文法(0型文法、无限制重写系统)
    如果P中的规则满足如下形式:α→β,α,β是字符串,则称G为无约束文法,或称为0型文法。

    如果一种语言能由几种文法产生,则把这种语言称为在这几种文法中受限制最多的那种文法所产生的的语言。

    (8)上下文无关文法产生的语言句子的派生树表示的步骤:
    CFG
    G = (N,sigma,P,S)

    1. 对于任意x∈N∪sigma,给一个标记作为节点,S作为树的根节点。
    2. 如果一个节点的标记为A,并且它至少有一个除他自身之外的后裔,则A∈N。
    3. 如果一个节点的标记为A,它的k(k>0)个直接后裔节点按照从左到右的次序一次标记为A1,A2,A3……Ak,则有A→A1A2……Ak一定是P中的一个产生式。

    派生树又称语法树、分析树、推导树
    一个栗子:

    在这里插入图片描述
    (9)上下文无关文法的二义性
    一个文法G,如果存在某个句子有不只一棵分析树与之对应,则称这个文法是二义的。
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

    2. 有限自动机与正则文法

    (1)确定的有限自动机

    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    (2)不确定的有限自动机

    在这里插入图片描述

    (3)确定的有限自动机和不确定的有限自动机的区别

    在这里插入图片描述

    (4)确定的有限自动机和不确定的有限自动机的关系

    在这里插入图片描述

    (5)正则文法与有限自动机的关系

    在这里插入图片描述
    在这里插入图片描述

    3 有限自动机在NLP中的应用

    (1)在NLP中,英语单词的拼写检查:
    设X为拼写错误的字符串,长度为m,Y为X对应的GT,长度为n。则X与Y 的编辑距离ed(X[m],Y[n])定义为:
    从字符串X转换到Y所需要的插入、删除、替换和交换两个相邻的基本单位字符的最小个数。
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述


    (2)对于有限状态机
    构造一个确定的有限状态机R,有定义R=(Q,A,δ,q0,F)
    其中Q表示状态集,A表示输入字符集,δ为QxA→Q的一个函数,q0∈Q,为起始状态,F包含于Q为终止状态集。

    当L包含于A*表示有限状态机R接收的语言,字母构成的所有合法单词都是有限状态机中的一条路径。当给定一个输入 串,对其进行检查的过程就是在给定阈值t(>0)的情况下,寻找那些与输入串的编辑距离小于t的路径。则一个字符串X[m]∉L能够被R识别的条件是存在一个非空集合C:
    在这里插入图片描述
    即存在一条L中存在的已知路径,该路径与X间的路径距离不大于t

    (3)单词拼写检查
    一般,英文单词可以使用键树(数字查找树)来存储。
    在这里插入图片描述
    在这里插入图片描述
    关于为何使用t作为变量,编辑距离中X长度的取值范围:
    若X的长度小于n-t,则X需要至少t+1次的增加操作才能达到与字符串Y相同;
    若X的长度大于n+t,则X至少需要t+1次的删除操作才能达到与字符串Y相同。

    仔细观察上图,关于阈值t,并非X与Y长度差的二分之一,而是我们前文中提到的,事先设定的阈值

    由此有了上图右下角的说明:
    关于阈值t的作用:是为了确定截取X的范围;进一步地,也能限制编辑距离(有可能小于阈值长度t)。

    一个栗子:
    在这里插入图片描述
    (4)关于采用深度优先搜索算法从自动机中选择路径:
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述在这里插入图片描述
    (5)关于使用有限自动机进行英语单词形态分析

    Note:在实际的应用中,除了有限状态机,还常常使用有限状态转换机(Finite State Transducer,FST)的概念。
    粗略的讲,有限状态转换机与有限自动机(有限状态机)的区别:
    有限状态转换机FST在完成状态转移的同时产生一个输出。而有限自动机FA或有限状态机FSM只实现状态的转移,而不产生任何输出。


    在这里插入图片描述

    可以观察到,在上述的状态转换过程中,有限状态转换机在状态转移的过程中,还产生了字符的输出。

    在这里插入图片描述
    在这里插入图片描述

    4 课后习题

    在这里插入图片描述

    (a)
    在这里插入图片描述
    (b)
    在这里插入图片描述

    在这里插入图片描述

    L ( G ) = a t + 1 ⋅ b t + 1 ⋅ c t + 1 L(G) = a^{t+1}·b^{t+1}·c^{t+1} L(G)=at+1bt+1ct+1

    在这里插入图片描述

    在这里插入图片描述

    展开全文
  • 哈尔滨工业大学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年《形式语言与自动机》期末试题

    1. Design a DFA for the language L = {w∈{0,1}* | w contains both 01 and 10 as substrings}.

    2. Design a NFA within four states for the language {a}*∪{ab}*.

    3. Design regular expressions for language over Σ = {0,1}.
      (1).All strings contain the substring 001.
      (2).All strings expect the string 001.

    4. Prove that L = {0m1n | m/n is an integer} is not regular with pumping lemma.

    5. Convert the following NFA into DFA with subset construction.
      在这里插入图片描述

    6. Give a context-free grammar for L = { aibjci+j|i,j>=0}

    7. Let L be the language generated by the grammar G below
      S->AB|BBB
      A->Bb|ε
      B->aB|A
      (1).消除空产生式
      (2).消除单元产生式
      (3).转换到CNF

    8. Design a PDA for L = {w∈{a,b}*|w has more a’s than b’s}

    9. Prove : for every context free language L, the language L’ = {0|w||w∈L} is also context free.

    10. 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.

    注:此题目为考试试卷实录,敬请放心食用。

    展开全文
  • 形式语言与自动机》(王柏、杨娟编著)课后习题答案
  • 形式语言与自动机

    2015-03-17 19:51:17
    课后习题答案,北邮出版社的,是王柏和杨娟老师的书,
  • 形式语言是研究自然语言和人工语言的数学工具,只研究组成规则,不研究语义;自动机理论研究抽象计算装置或“机器”。
  • 文档内包含部分课后习题和答案,仅供有需要的参考。
  • 形式语言与自动机理论+习题解答形式语言与自动机理论+习题解答形式语言与自动机理论+习题解答
  • 北邮形式语言与自动机二三章可够习题答案
  • 形式语言与自动机 第四章 课后答案

    千次阅读 多人点赞 2020-06-05 10:48:19
    形式语言与自动机 第四章 课后答案
  • 形式语言与自动机考题和习题,有近10来套和PPT讲稿。
  • 形式语言与自动机方法总结

    千次阅读 2020-07-14 23:02:59
    T6:正则语言转换DFA 最小化封闭性证明T7 文法设计,转换,化简T8 PDA设计T9 PDA 文法,转换,证明T10 图灵机设计 语言识别器 函数构造器 T1-3 DFA/NFA/正则表达式 设计 T4 正则语言泵引理 T5&T6: 正则语言...
  • 形式语言与自动机 第三章 课后答案

    千次阅读 多人点赞 2020-06-04 21:06:41
    P120 习题10, 14 考点:语言⇒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...
  • 是一个压缩文件,里面包含几份答案,需要的下载……
  • 形式语言与自动机答案

    热门讨论 2009-06-06 10:52:03
    这是自动机理论、语言与计算导论(第二版)的2-7章部分课后答案。
  • 帮助大家学好形式语言与自动机理论,对于计算机专业学生帮助很大。
  • 形式语言与自动机 答案 形式语言与自动机 答案 形式语言与自动机 答案 形式语言与自动机 答案

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,054
精华内容 421
关键字:

形式语言与自动机习题