Persuez's Blog

Thinking will not overcome fear but action will.

证明正则操作是封闭的

以下证明均用NFA证明,以下证明均只说证明思路,没有严格的数学论证。 正则语言在并操作中是封闭的。(The class of regular languages is closed under the union operation.) 思路:我们有两个正则语言$A_1$和$A_2$,并且想要证明$A_1 \cup A_2$也是正则语言。我们证明的思路是有两个NFA$N_1$和$N_2$分...

Nfa和dfa等价性证明

NFA和DFA等价转换

每个NFA都有一个等价的DFA 证明思路(NFA转DFA的方法) 我们要证明NFA和DFA等价,因为DFA是NFA的一般化,所以NFA一定可以模拟DFA,因此我们需要做的是用DFA模拟NFA。因为NFA在当前状态读到一个字符后可以有多条路可以走,所以模拟该NFA的DFA将有$2^k$个状态,每个状态都是NFA状态集的幂集的一个元素。具体操作在证明过程中。 证明 假设我们有一台NFA $N...

不确定性有限自动机

入门NFA

对比确定性有限自动机(DFA) DFA:当给定了当前所在状态,在遇到一个字符之后,我们就可以确定要向哪一个状态转移。打个比方,就是在我们当前位置没有岔路口,没有给我们多选的机会。 NFA:NFA即不确定性有限自动机(nondeterminism finite automaton),它允许我们在遇到一个状态时可以有多条转移路径可以选择。特殊的是,它允许我们不读入任何字符就进行状态转移(此操作称...

证明regular operation中的union操作是封闭的

证明regular operation中的union操作是封闭的

证明思路 $M_1$和$M_2$是两个DFA,且$L(M_1)=A,L(M_2)=A_2$,现在要证明存在一个DFA$M$可以recognizes $A \cup A_2$(我们将会找到这样一个DFA,而不仅仅是存在),即$L(M)=A \cup A_2$。我们找这样一个DFA的方法是通过模拟simulate。但是在读到一个字符时,我们的DFA要往哪个状态转移呢?DFA不允许我们遇到一个字符...

确定性有限自动机

确定性有限自动机(Deterministic Finite Automaton, DFA)

形式化定义 我们用5元组$(Q,\sum,\delta,q_0,F)$定义确定性有限自动机 $Q$是状态的有限集 $\sum$ 是字母表 $\delta$是转移函数,映射关系为$Q×\sum \rightarrow Q$ $q_0$表示开始状态 $F \subseteq Q$是accept状态集 既然有了以上定义,接下来定义一个DFA$M$ ac...

汇编前导篇

80x86家族CPU简介

这篇博文用来记录对硬件理解方面的一些困惑和一些80x86系列CPU的基础知识。 CPU时钟(clock, clock pulse, clock rate, cycle) 时钟(clock): 计算机(CPU)用时钟来同步(synchronize)CPU执行的指令。(不明白继续往下看) 时钟脉冲(clock pulse)和时钟频率/时钟频率速度(cloc...

操作系统定义

为什么会有这篇博文 这篇博文只从标题来看会觉得很无聊(确实也是这样),并且会觉得没有必要。可是如果别人问你操作系统的主要作用是什么?你会很棒的回答,还是支支吾吾呢!下面进入正题。 思路 人类的思考一般要么是自顶向下(国人的思维方式)(国外),要么是(自底向上)(国外)。 隐藏硬件(自顶向下) 资源管理(自底向上) 隐藏硬件(将丑陋转变为美丽) 这里涉及到一个关键名词:抽象。我想...

C程序设计语言

C语言变长参数表

C语言变长参数表 标签(空格分隔): ANSI C 变长参数 标准输出 声明格式,如printf函数: int printf(char *fmt, ...) 其中,省略号表示参数表中的参数的数量和类型是可变的。**注意:省略号只能出现在参数表的尾部,即函数的声明中必须至少有一个显式声明的参数,如printf中的char *fmt参数。 变长参数表的使用(处理) #includ...