形式语言与自动机:大纲与摘要

这一系列(共 4 部分)为整理后的形式化语言与自动机的本科课程笔记,可作为知识提纲。 I:概念,推理与文法 核心问题:哪些问题可以通过计算解决(可计算型理论) 自动机理论:研究抽象机器所能解决问题的理论(图灵机:核心理论模型;以及有限状态机、文法、下推自动机等) 谓词逻辑与集合关系 „n元关系是定义在某域上的一组n元组的集合 „集合A和B的二元关系R是A×B的子集;二元关系可写作 xRy „dom(R)和ran(R)分别表示关系R的定义域和值域 对于 $R \subseteq S\times S$ 几种特殊的关系: 偏序关系:自反,反对称,传递 Eg. 自然数集合N和小于等于关系≤构成的偏序集 等价关系:自反,对称,传递 -> 等价类:由等价关系确定的一组集合,每个集合中的任意元素都相互等价 „等价关系的秩:等价类的个数 字母表、图与语言 字母表是语言中出现的原子符号,通常用Σ表示 字符串是字母表中元素的序列,长度必须为有限的,长度、连接等操作在定义上都为递归 长度:递归定义 $|w| = 0, w = \varepsilon; |x| + 1, w = xa$ „字符串运算:„联结运算 abc.def、„重复运算 (abc)* 和集合有关的运算:$A \cdot B = {w | w = x \cdot y, x\in A, y \in B}$ 若 $\Sigma$ 为字母表,则 $\Sigma^n$ 为长度为 n 的字符串集合 正闭包、克林闭包 „语言:一系列特殊字符串的集合:„L⊆Σ^∗ 图:系统描述方式 „标签集合D,标签函数 L:S∪T→D „带标签的图可以表示为一个4元组 (S,T,D,L) 树是一种特殊的有向无环图 迁移系统:$TS = (s, \Sigma,\rightarrow,S_0)$ 给定字符串是否属于某个具体语言 L? 任何问题都可以转换成语言问题 $w \in L?...

September 3, 2020 · Bill Chen

关于函数依赖,正则覆盖与 BCNF 范式分解

复习数据库系统时刚好接触到这部分内容。有几个相对重要而难理解的概念,教材的语言十分形式化,在这里稍作一下直观的整理。 函数依赖 Functional Depencendy 可以理解为属性 R 中的一个元组 t1 (这个元组需要是这个关系的 super key,即能够标识整个属性集合)决定了另一系列元组 t2 的值。例如部门决定了预算,则有函数依赖 $dept \rightarrow budget$。 函数依赖分为平凡函数依赖和非平凡函数依赖。函数依赖 $X \rightarrow Y$ 中,若 Y 为 X 的子集,则为平凡函数依赖。直观的字面理解就是这种依赖非常的 “普通”,在所有关系中都满足。例如任何属性都能决定自身,函数依赖 $A \rightarrow A$ 恒成立。若 Y 不为 X 的子集,则为非平凡函数依赖。通常我们讨论的是非平凡函数依赖。 完全函数依赖指的是 $X \rightarrow Y$ 中,X 已经包含了最少的属性。再减少任何一个属性都会破坏函数依赖。例如预算可以完全依赖于部门和年份,这就是一个完全依赖。 而部分函数依赖指的是在 $X \rightarrow Y$ 仍然存在 X 的子集 X' 满足 $X' \rightarrow Y$,例如 $dept_id, dept_name \rightarrow budget$ 中,左侧仅依赖 dept_id 就可以决定预算的值,那么这就是一个部分函数依赖,预算部分依赖于部门 ID 和部门名字。 还有一个传递函数依赖的概念,如果 $X \rightarrow Y$,$Y \rightarrow Z$,则 $X \rightarrow Z$ 成立。这就是一个传递函数依赖。如员工 -> 部门 ID,部门 ID -> 预算,那么员工 -> 部门预算就是一个传递函数依赖。...

August 31, 2020 · Bill Chen

拟物与抽象——设计也是一个循环

WWDC2020 来了,Big Sur 的视觉方案又一次走在了最前面。 熬夜看完了 WWDC2020。Apple 的自研处理器自然是发布会的高潮,不过除此之外,与新处理器一起到来的还有 macOS 10.X 时代的终结 —— 有生之年这个版本号终于上 11 了。之所以在题目里说「设计是一个循环」,是因为这套来自 Big Sur 的图标设计方案实在是太让人梦回 20 年前了。正好最近有空,遂整理在 UI 设计上,设计师们是怎么走了一个圈又回来了。 开始的开始 高光,阴影,强渐变制造出的立体感 —— Aqua Design。 在计算机刚飞入寻常千万家的二十世纪末,现在看起来非常习以为常的界面元素可能对于普通用户而言并不好理解。因此,这样一个「看起来就可以点击」的界面元素就是在告诉用户:这就是一个按钮;水滴一样的问号球,也是在对用户大声地说:「有什么不懂的,点我」。 同时,更强的图像处理能力也鼓励设计师在 UI 上「炫技」,用复杂的纹理和过渡动画来展现出精致得到效果。乔布斯曾对于这套将深度、高光首次引入 GUI 的设计方案这样评价: Its liquid, one of the design goals was when you saw it you wanted to lick it. 同时期的 Windows XP, Vista 再到 Win7,五一不是在类似地尝试还原这种真实的质感。毛玻璃展现出来的层级划分,水灵灵的图标质感,是这个时代最典型的设计风格。 扁平化 随着大家渐渐熟知了界面交互的种种共识,也就不再需要通过直观的视觉细节来了解 UI 元素的作用。于是从 2010 年起,各家巨头都陆陆续续开始走上了扁平的道路。 Jony Ive 担任苹果首席设计师的第一个作品,就是 iOS 7,也就是那个把 iOS 6 之前把拟物做到极致的系统完全拍扁的版本。第二年, Yosemite 发布。这一略带质感的扁平风格,成了大多人现在所熟知的 macOS 的形态。...

June 26, 2020 · Bill Chen

使用 Flask 实现微信公众号自动回复 Bot

人都是被逼出来的,业务突然来了的时候才能感到全速赶工的效率。这里记录一下如何用 10 分钟快速配置一个微信公众号自动回复机器人。 一些准备工作 首先需要关闭微信提供的自动回复功能,然后登录微信公众平台,前往开发者配置的基本配置。 URL :在这里输入你的接口地址,在下方的例子中,是 https://url/wechat。 Token:你可以自己输入 Token,用于验证。 EncodingAESKey:随机生成就好,同样用于验证。 消息加密方式:只要采用了 https 协议,明文模式也已经足够安全。为了便于开发调试我直接使用了明文方式。 快速让后端跑起来 需求很重要。没有必要在部署和非逻辑层上花费太多时间。下面是我使用的框架,在 get_reply(msg) 中写下你的业务逻辑就好。 对于比较复杂的项目,你可以考虑把一些方法拆分单独的文件中。 import hashlib from flask import * import xml.etree.ElementTree as ET app = Flask(__name__, static_url_path='/static') WECHAT_TOKEN = 'YOUR TOKEN' AES_KEY = 'YOUR AES KEY' def get_reply(msg): return 'You can write your own handler here.' def send(to_user, from_user, content): reply = """ <xml><ToUserName><![CDATA[%s]]></ToUserName> <FromUserName><![CDATA[%s]]></FromUserName> <CreateTime>%s</CreateTime> <MsgType><![CDATA[text]]></MsgType> <Content><![CDATA[%s]]></Content> <FuncFlag>0</FuncFlag></xml> """ response = make_response(reply % (to_user, from_user, str(int(time....

May 4, 2020 · Bill Chen

『NexT』:一款 NexT 风格的 Typora 主题

很喜欢 Hexo 中的 Next 主题,便想要在 Typora 中书写时获得和在 Hexo 中一样的预览效果,便写了这样一个主题。 Features 对于中文字体,我使用了浙江大学科技设计创新创业实验室开发的未来荧黑字体(https://github.com/welai/glow-sans)。实测下来这款字体在高 DPI 屏幕下显示效果较好,不过在标准的屏幕上效果一般。 英文字体使用的 Overpass(http://overpassfont.org/),风格类似于 SoundCloud 的御用字体 Interstate。这款现代化的字体的灵感来自于联邦高速公路体 Highway Gothic,具有极高的辨识度和易读性。 等宽字体使用了 JetBrains 在 2020.1 系列 IDE 引入的默认字体 JetBrains Mono。整体风格维持了 NexT 主题的 Muse Scheme,对代码框,下划线,引用和链接等做了适配,移植了表格、分割线的样式,同时微调了侧栏的样式。不过由于大多数时间都在 macOS 下调试,Windows 上有概率出现一些意想不到的问题。 由于我在平时涉及到 Markdown 的写作工作大多是技术文档,夹杂较多的代码和列表,所以在设置间距的时候,我额外考虑了连续的多个段落的排版情况,所以避免出现了当列表较多的时候间距过大的问题。 Preview 和原本的 NexT 主题相比,稍微调了一下行内代码的高亮颜色,这里放几张效果图: 后来额外适配了一个暗黑主题: Link http://theme.typora.io/theme/NexT/ https://github.com/BillChen2K/typora-theme-next 字体无需手动安装,已包含在主题内。这里 提供了安装方法。 如果需要使用 Helvetica 版本的主题,需要一并复制标准版本的 css 文件,因为是直接 import 进来的。

May 1, 2020 · Bill Chen