首页 > 其他分享 >《自动机理论、语言和计算导论》阅读笔记:p402-p427

《自动机理论、语言和计算导论》阅读笔记:p402-p427

时间:2024-05-05 23:45:17浏览次数:28  
标签:p402 语言 p427 导论 predominantly https 自动机

《自动机理论、语言和计算导论》学习第 13 天,p402-P427总结,总计 26 页。

一、技术总结

无。

二、英语总结

1.elude

e--,assimilated form of ex-(out, away) + ludere(to play, see ludicrous)。vt. if sth you want eludes you, you do not succeed in achieving it。

p426, Moreover, an important consequence of intractability

2.predominantly

(1)predominant: pre-(before) + *dem-(house, household)。adj. more noticable or important than others; being the most noticable。

(2)predominantly: adv. mostly or mainly。

p426, We shall be interested predominantly in the case where T(n) is a polynomial in n。

三、其它

无。

四、参考资料

1. 编程

(1)Eric S.Roberts,《自动机理论、语言和计算导论(英文版.第3版)》:https://book.douban.com/subject/2274854/

2. 英语

(1)Etymology Dictionary:https://www.etymonline.com

(2) Cambridge Dictionary:https://dictionary.cambridge.org

欢迎搜索及关注:编程人(a_codists)

标签:p402,语言,p427,导论,predominantly,https,自动机
From: https://www.cnblogs.com/codists/p/18174111

相关文章

  • 《自动机理论、语言和计算导论》阅读笔记:p352-P401
    《自动机理论、语言和计算导论》学习第12天,p352-P401总结,总计50页。一、技术总结1.TuringMachine(TM)2.undecidability​a.Ld(thediagonalizationlanguage)3.reductionp392,Ingeneral,ifwehaveanalgorithmtoconvertinstancesofaproblemP1toi......
  • 字符串基础(hash,KMP,AC自动机,trie)
    trie树trie树,又叫字典树,就是把字符串的每个字母看做树上的一个节点,若干个字符串组成了一棵trie树。最一般的trie树好像只能搜索字符串,重点是01trie和可持久化trie树和用trie树来建ac自动机(详见AC自动机)。这里着重介绍一下01trie01trie,就是节点代表了数上的二进制位上的数。......
  • 《自动机理论、语言和计算导论》阅读笔记:p215-p351
    《自动机理论、语言和计算导论》学习第11天,p215-p351总结,总计37页。一、技术总结1.constrainedproblem2.Fermat'slatstheoremFermat'sLastTheoremstatesthatnothreepositiveintegersa,bandcsatisfytheequationa^n+b^n=c^nforanyintegervalue......
  • 后缀自动机
    存储子串的出现次数怎么把这个子串打印出来呢?#include<cstdio>#include<cstring>#include<string>#include<cmath>#include<algorithm>#include<iostream>usingnamespacestd;inttot=1,las=1;structNODE{intch[26];intlen,fa;......
  • 《自动机理论、语言和计算导论》阅读笔记:p261-p314
    《自动机理论、语言和计算导论》学习第10天,p261-p314总结,总计48页。一、技术总结1.generating&reachable2.ChomskyNormalForm(CNF)乔姆斯基范式。3.pumpinglemma泵作用引理。引理:引理是数学中为了取得某个更好的结论而作为步骤的已证明命题,其意义并不在于自身已完......
  • 回文自动机
    求以每个节点结尾的,回文子串的个数,最大回文子串的长度求回文串的总个数(必须连续)不连续的是动态规划#include<bits/stdc++.h>usingnamespacestd;constintmaxn=500005;charstr[maxn];structPAM{intsize,last,r0,r1;inttrie[maxn][26],fail[maxn],l......
  • AC自动机
    二次加强版那个题距离最大内存,就差了一个ss数组了....96分#include<bits/stdc++.h>#definemaxn2000001usingnamespacestd;stringss[100000];chars[maxn],T[maxn];intn,cnt,vis[200051],ans,in[maxn],Map[maxn];structkkk{intson[26],fail,flag,ans;voi......
  • 【学习笔记】 字符串基础 : 后缀自动机(基础篇)
    本文只介绍关于\(\mathbf{SAM}\)的基本概念与实现后缀自动机是什么类似\(\text{AC}\)自动机,后缀自动机(\(\text{SAM}\))是能且只能接收字符串所有后缀的自动机我们首先要知道,\(\mathbf{SAM}\)是只能接收所有后缀的结构而不是只能维护后缀的结构事实上\(\mathbf{SAM}\)......
  • 《自动机理论、语言和计算导论》阅读笔记:p139-p171
    《自动机理论、语言和计算导论》学习第7天,p139-p171总结,总计33页。一、技术总结1.reversalp139,Thereversalofastringa1a2...anisthestringwrittenbackwards,thatisanan-1...a1.2.homomorphismAstringhomomorphismisafunctiononstringsthatwokrs......
  • AC 自动机
    参考博客:常见字符串算法II:自动机相关前置知识AC自动机结合了KMP和字典树的思想,将匹配放到字典树上,构建fail指针,实现多模匹配。先对模式串构建Trie。字典树上的一个节点对应了模式串的一个前缀,我们称其为一个状态。状态\(u\)的失配指针\(\text{fail}(u)\)指向状态......