This article does not have a corresponding language version
从Regex直接构造DFA
2026-07-12 481 words 3 mins

从Regex直接构造DFA

关于NFA的重要状态 我们将具有非ε出转移的NFA状态称为NFA的重要状态(Important state)。这里我直接贴定义原文了，这个好理解。 Importance State: We call a state of an NFA important if it has non-ϵ out-transition. 如何判定两NFA States相等 拥有完全相同的Importance states 要么都有Accept State，要么都没有。 相关算法的回顾 我们来回顾一下Regex-NFA的算法，看看如何跳过NFA直接到DFA。回顾一 …
正则表达式到NFA的转换
2025-12-18 96 words 1 min

正则表达式到NFA的转换

EDIT (2025-12-09): 添加了算法的生成的NFA节点与转移数量的结论的说明. 简要介绍 正则表达式Regex可以转换到NFA，然后可以直接模拟NFA或将所得NFA转换到DFA再模拟。这样就是一个完整的正则匹配引擎了。 参考博文 本文是词法分析系列第三篇文章，主要介绍从regex转换到NFA的方法。关于如何模拟运行NFA请参考下面两篇文章： 直接模拟NFA：NFA的模拟运行 先将NFA转换到DFA再模拟：NFA到DFA的转换算法 将正则表达式转换到NFA(本文) 算法! 这个算法又被称为McNaughton-Yamada-Thompson Algorithm （好长的名字！） …
Start to learn ARM64 ASM! - S1E1 - Installing the qemu for aarch64 on x86-64 archlinux
2025-11-27 665 words 4 mins

Start to learn ARM64 ASM! - S1E1 - Installing the qemu for aarch64 on x86-64 archlinux

Goal This post shows how to install aarch64 qemu simulator on x86-64 and run a simple program on aarch64. Step 1: Installing prerequisites for qemu-system-aarch64. Basically, you will need to install the following packages into your x86-64-based host system. qemu-system-aarch64: For the emulator …
NFA的模拟运行
2025-08-09 388 words 2 mins

NFA的模拟运行

EDIT1：更新原始算法的时间复杂度估计 EDIT2：更新优化后的算法实现 EDIT3: 重写了优化后的代码及代码分析。 EDIT4: 重写代码复杂度分析 NFA的基础 NFA的概念、构成要素可以参考这篇文章. 本文主要讨论如何模拟NFA. 模拟NFA的算法 ALGORITHM: NFA Simulation 的经典算法 算法 INPUT: 输入字符串str NFA nfa. OUTPUT: ACCEPT / REJECT. def sim_nfa(nfa, str): (s0, F) = nfa # NFA的开始状态s0和终结状态F S = ϵ-closure(s0) # 计 …
NFA到DFA的转换算法
2025-08-08 407 words 2 mins

NFA到DFA的转换算法

EDIT(2025-12-01): 添加了对ϵ转移的说明。隔了一段时间再看居然有些看不懂ϵ转移了，赶紧复习了下，新增了说明备忘。 EDIT2(2025-12-18): 扩充FA的说明，添加算法优化思路及时间复杂度分析。 EDIT2(2025-12-18): 扩充DFA的说明，添加Dead State. EDIT3(2025-12-29):修改了算法伪代码, 修正了算法时间复杂度分析(原来的分析是错的!). EDIT4(2026-03-13): 扩充文章内容，解释算法的目的。 常见概念的说明 首先需要对本文用到的概念进行说明. 如果你已经对下述概念很熟悉,可以跳过本节. 什么是FA：FA即有限自 …
Hello World
2025-08-07 4 words 1 min

Hello World

💘 博麗 霊夢 💘