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

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

时间:2024-04-13 23:45:08浏览次数:29  
标签:string p171 导论 p139 https 自动机

《自动机理论、语言和计算导论》学习第 7 天,p139-p171总结,总计 33 页。

一、技术总结

1.reversal

p139, The reversal of a string a1a2...an is the string written backwards, that is anan-1...a1.

2.homomorphism

A string homomorphism is a function on strings that wokrs by substituting a particular string for each symbol。

二、英语总结

1.contrapositive

(1)contra: against, opposite, on the opposite side。

(2)contraposition:contra(against) + position(to put, place), 。

(3)contrapositive:contrapositition + -ive,adj. pertaining to contraposition。

2.dominant

-dem*(house, household)。adj. more strong than anything else of the same type。

3.set-bracket

{ }

三、其它

四、参考资料

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)

标签:string,p171,导论,p139,https,自动机
From: https://www.cnblogs.com/codists/p/18133593

相关文章

  • AC 自动机
    参考博客:常见字符串算法II:自动机相关前置知识AC自动机结合了KMP和字典树的思想,将匹配放到字典树上,构建fail指针,实现多模匹配。先对模式串构建Trie。字典树上的一个节点对应了模式串的一个前缀,我们称其为一个状态。状态\(u\)的失配指针\(\text{fail}(u)\)指向状态......
  • 《自动机理论、语言和计算导论》阅读笔记:p115-p138
    《自动机理论、语言和计算导论》学习第6天,p115-p138总结,总计24页。一、技术总结1.associativityandcomutativity(1)commutativity(交换性):Commutativityisthepropertyofanoperatorthatsayswecanswitchtheorderofitsoperandsandgetthesameresult.......
  • 后缀自动机 SAM
    后缀自动机SAM#算法SAM满足如下性质有向无环图每个转移只有一个字符接受且只接受\(S\)的后缀节点数在满足上述条件下最小考虑不满足性质\(3\),那么\(trie\)就可以做到将这个\(trie\)建出来后,发现有很多完全相同的子树定义\(endpos(s)\)表示串\(s\)在\(S\)......
  • 《自动机理论、语言和计算导论》阅读笔记:p68-p114
    《自动机理论、语言和计算导论》学习第4天,p68-p114总结,总计47页。一、技术总结1.invertedindexes明白单词的意思是“反转的索引”,但是不明白其在书中具体指什么,去查询资料的话需要花很不多时间,先继续往下看。遇到这种场景的可能性还是比较多的。2.lexicalanalysis(1)lexico......
  • 后缀自动机的一些题目的整理
    后缀自动机的一些题目的整理P3804【模板】后缀自动机(SAM)P3804【模板】后缀自动机(SAM)板子题,没啥好说的。#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;constintN=2e6+5;inttot=1,last=1,idx,n;intver[N],h[N],ne[N];chars[N];llf[N],ans......
  • 《自动机理论、语言和计算导论》阅读笔记:p49-p67
    《自动机理论、语言和计算导论》学习第4天,p49-p67总结,总计19页。一、技术总结1.DeterministicFiniteAutomata(DFA)vsNondeterministicFiniteAutomata(NFA)(1)DFA定义(2)NFA定义A"nonedeterministic"finiteautomatahasthepowertobeinseveralstatesatonce......
  • AC自动机学习笔记
    AC自动机有两个前置知识点,KMP算法和字典树KMP算法:KMP(Knuth-Morris-Pratt)算法是一种高效的字符串匹配算法,由DonaldKnuth、VaughanPratt和JamesH.Morris于1977年共同发明。KMP算法的核心思想是当字符串不匹配时,能够利用已经部分匹配的信息,避免从头开始匹配,从而提高匹配效率......
  • 《自动机理论、语言和计算导论》阅读笔记:p1-p4
    《自动机理论、语言和计算导论》学习第1天,p1-p4,总计4页。这只是个人的学习记录,因为很多东西不懂,难免存在理解错误的地方。一、技术总结1.有限自动机(finiteautomata)示例1.softwareforcheckingdigitalcircuits。2.lexicalanalyzerofcompiler。3.softwareforscannin......
  • P1712 [NOI2016] 区间 线段树+双指针
    //Problem://P1712[NOI2016]区间////Contest:Luogu//URL:https://www.luogu.com.cn/problem/P1712//MemoryLimit:250MB//TimeLimit:1000ms////PoweredbyCPEditor(https://cpeditor.org)#include<iostream>#include<algorithm......
  • 4.13 ACM-ICPC算法 字符串之后缀自动机
    4.13ACM-ICPC算法:字符串之后缀自动机在竞赛编程,尤其是ACM-ICPC竞赛中,字符串算法占据了极其重要的位置。其中,后缀自动机(SuffixAutomaton,简称SAM)以其强大的功能和高效的性能,成为了解决字符串问题的利器。本文旨在介绍后缀自动机的基本概念、构建方法以及在算法竞赛中的应......