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

这一系列(共 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

使用 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

数据库常用关系代数符号在 LaTeX 中的表示

Relational Algebra / 关系代数符号可以用于表达数据库标准操作逻辑。近期做数据库作业时经常需要用 $\LaTeX$ 表示关系代数的符号,故在这里稍作整理。 Operation 中文 符号 $\LaTeX$ Projection 投影 $\Pi$ \Pi Selection 选择 $\sigma$ \sigma Renaming 重命名 $\rho$ \rho Aggregate Function 聚合函数 $\mathcal{G}$ \mathcal{G} Union 交 $\cap$ \cap Intersection 补 $\cup$ \cup Natural Join 自然连接 $\bowtie$ \bowtie Left Outer Join 左外连接 ⟕ … 这几个直接复制吧 Right Outer Join 右外连接 ⟖ Full Outer Join 全外连接 ⟗ Cartesian product 笛卡尔乘积 $\times$ \times Divide 除 $\div$ \div Assignment 赋值 $\leftarrow$ \leftarrow And 条件并列 $\land$ \land or \vee Negation 非 $\neg$ \neg Exist 存在 $\exists$ \exists For All 对所有 $\forall$ \forall 下标文字 $\sigma_{\text{username}}$ _{\text{}} 粗体文字 $\mathcal{G}_{\textbf{count(*)}}$ \textbf{} 长长长长括号 $\big( \Big( \bigg( \Bigg($ \big( \Big( \bigg( \Bigg( 比较 $\gt \ge \lt \le \ne$ \gt \ge \lt \le \ne 一个栗子🌰:...

April 15, 2020 · Bill Chen

使用 Python 自动登录华东师范大学数据库

近期经常需要写一些和华师大数据库交互的小工具,比如导出课程表,获取绩点等。这里提供使用 Python 登录数据库的方法,将登录信息使用 request 包记录在一个 request.session 中。 这里涉及到四个函数。 main():一个示例的交互逻辑 ECNULogin()主要的登录函数 GetCode()用于获取验证码。这里把手动输入的两行注释掉了,如果不想安装tenserflow,则可以注释掉下面的识别部分,手动输入验证码。不过华师大的验证码很好识别。目前我还没有遇到 pytesseract识别失败的情况。 GetRSA()RSA 加密登录信息。这里调用的是华师大数据库中的 js 文件,并使用execjs来调用内部的 strEnc 函数。 from PIL import Image # 手动输入验证码 import pytesseract # 自动识别验证码 from lxml import etree import sys import requests import getpass import execjs # 用于加密 # 记录登录信息的 session s = requests.session() mainurl = 'https://portal1.ecnu.edu.cn/cas/login?service=http%3A%2F%2Fapplicationnewjw.ecnu.edu.cn%2Feams%2Fhome.action' headers = { 'User-Agent': 'Mozilla/5.0 (Macintosh; Intel Mac OS X 10_14_3) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/73.0.3683.103 Safari/537.36', 'Refer': 'https://portal1....

April 15, 2020 · Bill Chen