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

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

Airport Simulation (数据结构与算法 - 队列 / Queue 的应用)

Airport Simulation 是数据结构与算法教材中用于演示Queue的一个小程序(大多数教师似乎会跳过这个练习)。主程序会通过输入总的运行时间、队列里可以等待的最多飞机数量,平均每个时间单元到来的飞机和离开的飞机(提供泊松分布的均值生成随机数)。 运行效果 程序的结构不算复杂,利用Runaway类来封装两个landing和takeoff队列,处理飞机的请求和行为;Plane类来封装飞机的状态和信息,以及在受到指令时输出信息到控制台。只是教材里的讲述有些分散,运行效果也由于输出太多而显得凌乱无比。练习布置许久之后也是一直没有找到一整块时间写完这个练习。这里是前几天完成的一个经过输出优化后的程序,格式比较易于观测。 该程序应在Linux或macOS下编译。在Windows下编译由于不支持彩色输出会出现一些奇怪的转移序列,sleep函数和usleep函数也应当用windows.h中提供的方法实现。 main.cpp和Random.h的源代码如下。其中Random.h用于提供泊松分布的随机数生成,参考自CSDN。 你可以在这里直接下载:https://cloud.billc.io/s/FeLekECBFKb6GkF #include <iostream>#include <queue>#include <unistd.h>#include "Random.h"using namespace std; typedef int feedback; const int success = 1; const int fail = 0; const int USPEED_SHORT = 1000; const int USPEED_LONG = 1000; enum flightStatus{ null, toLand, toTakeoff }; enum runawayAct{ idle, letTakeoff, letLand }; string percentage(int A, int B){ char *temp = new char[100]; sprintf(temp, "%3.2f%%", (double)A / (double)B * 100); string output = temp; return output; } class Plane{ private: int ID; int comingTime; flightStatus status; public: Plane(){ ID = -1; comingTime = -1; status = null; } Plane(int _ID, int _comingTime, flightStatus _status){ usleep(USPEED_SHORT); ID = _ID; comingTime = _comingTime; status = _status; cout << "[PLANE MESSAGE] Plane NO....

March 29, 2019 · Bill Chen