# 有限状态机 Mealy Moore 卡诺图最小化教学器

逐步讲解自动机与组合逻辑：ε-NFA→NFA→DFA 子集构造、Moore 划分细化最小化、Mealy↔Moore 输出映射互转；卡诺图 Gray 排序分组与 Quine-McCluskey 素蕴含项 + 精确最小覆盖求最小 SOP。输出含 ASCII 状态图、转换表与每轮迭代。

> 标准页面: https://elysiatools.com/zh/tools/finite-state-machine-mealy-moore-karnaugh-minimization-tutor

- **分类:** Education

- **关键词:** 有限状态机, 自动机, 卡诺图, 奎因麦克拉斯基, 最小化, 离散数学, 数字电路

## 概述

自动机 DSL：`states: q0 q1 …`、`start: q0`、`accept: q1, q2`、`alphabet: a b`，转移每行一条 `起点 符号 终点`（ε 边写 ε 或 eps）；Mealy 输出写作 `q0 a q1 / 1`，Moore 输出用 `moore: q0:0 q1:1` 声明。子集构造对 ε-NFA 先求 ε-闭包；最小化先删除不可达状态再做 Moore 划分细化（这是经典陷阱）；Mealy→Moore 按进入输出拆分状态（至多 |Q|·|Δ| 个）。布尔模式：Quine-McCluskey 相邻组合并（差一位、对齐连字符），素蕴含项图表只覆盖 ON 集最小项，本质素蕴含项后用穷举子集求精确最小覆盖（Petrick 等价）。参考用例 (a|b)*abb 的 ε-NFA 已验证：5 态 DFA、4 态最小 DFA；Σm(0,1,2,5,6,7,8,9,10,14) 的唯一最优解为 B'C' + CD' + A'BD。

## 输入项

- **模式** (select)
- **自动机定义** (textarea): states: q0 q1 q2 start: q0 accept: q2 alphabet: a b q0 a q0 q0 b q0 q0 ε q1 q1 b q2 q2 a q2 q2 b q2
- **变量个数（卡诺图）** (number)
- **最小项（ON 集）** (text): 0,1,2,5,6,7,8,9,10,14
- **无关项** (text): e.g. 3,11,12
- **NFA 转 DFA（子集构造）** (checkbox)
- **最小化 DFA（Moore 划分细化）** (checkbox)
- **Mealy ↔ Moore 互转（若提供输出）** (checkbox)

## 适用场景

- 需要将 ε-NFA 或 NFA 转换为 DFA，并查看 ε-闭包、子集构造和转换结果时。
- 需要删除不可达状态并通过 Moore 划分细化求最小 DFA 时。
- 需要使用卡诺图和 Quine-McCluskey 方法，根据最小项与无关项求精确最小 SOP 时。

## 工作原理

- 在自动机模式中输入 states、start、accept、alphabet 以及逐行转移；ε 边可写作 ε 或 eps，Mealy 输出可写在转移后，Moore 输出用 moore 声明。
- 启用 NFA 转 DFA 后，工具先计算 ε-闭包，再执行子集构造，并生成状态图和转换表。
- 启用最小化后，工具先移除不可达状态，再通过 Moore 划分细化逐轮区分状态。
- 在布尔模式中输入变量个数、ON 集最小项和可选无关项，工具按 Gray 顺序分组并通过 Quine-McCluskey 求素蕴含项和精确最小覆盖。

## 使用案例

- 离散数学课程中演示 ε-NFA、NFA、DFA 的转换过程和 DFA 最小化步骤。
- 数字电路设计中使用卡诺图与 Quine-McCluskey 方法化简组合逻辑函数。
- 复习 Mealy、Moore 状态机的输出映射、状态拆分和转换表构造。

## 常见问题

### 自动机定义需要使用什么格式？

使用 states、start、accept、alphabet 头部声明，并按“起点 符号 终点”每行输入一条转移。

### 如何表示 ε 转移？

在转移中使用 ε 或 eps 作为符号，例如 `q0 ε q1`。

### 工具可以最小化 DFA 吗？

可以。启用“最小化 DFA”后，工具会先删除不可达状态，再进行 Moore 划分细化。

### Mealy 和 Moore 输出如何输入？

Mealy 输出写作 `q0 a q1 / 1`；Moore 输出使用 `moore: q0:0 q1:1` 声明。

### 布尔最小化需要输入哪些内容？

选择变量个数，输入 ON 集最小项，并可选填无关项，例如 `0,1,2,5`。

## 相关工具

- [氨基酸组成分析器](https://elysiatools.com/zh/tools/amino-acid-composition): 分析一条氨基酸序列的组成：20 种标准氨基酸各自的计数与摩尔百分数；分组统计（碱性 K/R/H、酸性 D/E、芳香族 F/W/Y、含硫 C/M、脂肪族 A/I/L/V、酰胺侧链 N/Q、羟基 S/T、其他 G/P）；按 Kyte–Doolittle 1982 疏水值计算 GRAVY 平均疏水指数（>0 偏疏水、<0 偏亲水，可溶性球状蛋白通常介于 −1 至 +0.3）；并附 ProtParam 平均质量表的分子量。歧义码（B/J/O/U/X/Z）单独计数、不计入百分比。来源：Kyte & Doolittle 1982、ExPASy ProtParam、Lehninger。仅供教学与实验规划。
- [种群瓶颈效应模拟器（杂合度衰减）](https://elysiatools.com/zh/tools/bottleneck-effect-simulator): 模拟种群瓶颈后的期望杂合度损失（确定性期望）。理想 Wright-Fisher 漂变下每代 H_{t+1} = H_t(1 − 1/(2N))，故 H_final = H₀(1−1/2Nb)^t × (1−1/2Nr)^g；调和平均有效种群大小 Ne = (t+g)/(t/Nb + g/Nr) 由最小瓶颈主导；相对基础群体的累积近交系数 F = 1 − H_final/H₀。对频率 p 的目标等位基因，单代瓶颈存活概率 = 1 − (1−p)^(2Nb)，稀有等位基因最先丢失。经典案例：北象海豹（1890 年代约 20 只幸存 → 近零变异）、猎豹、夏威夷雁、欧洲野牛、平格拉普环礁。来源：Wright 1931、Nei et al. 1975、Hartl & Clark 2007、StatPearls。仅供教学用途。
- [词频表 SRS 牌组生成器](https://elysiatools.com/zh/tools/language-vocab-spaced-repetition-deck-generator): 粘贴双语词频表，导出 Anki 兼容牌组，自动把每条拆成识别 / 回忆 / 完形填空三类卡片，附带词性、IPA 与例句，并给出 SM-2 间隔预览。
- [限制酶切片段长度计算器](https://elysiatools.com/zh/tools/restriction-fragment-length): 估算限制酶消化后的片段大小：环状底物 n 个切点产生 n 个片段（绕原点环绕），线性底物 n 个切点产生 n+1 个片段。切点位置模式按逗号分隔的坐标精确计算各片段；切点数目模式按平均分布给出片段数与均值。附带随机 DNA 识别位点频率：4 碱基识别子约每 256 bp 一个、6 碱基约每 4096 bp 一个（REBASE/Sambrook），以及琼脂糖凝胶分辨率提示（<50 bp 可能跑丢）。来源：Sambrook & Russell 第 3 版、REBASE。仅供教学与实验规划。
- [AsciiMath / LaTeX / MathML 公式转换器](https://elysiatools.com/zh/tools/asciimath-latex-mathml-equation-converter): 在 AsciiMath、LaTeX 与 MathML 之间互转公式：自动识别输入格式，输出规范 LaTeX、带语义注记的 Presentation MathML、尽力而为的 AsciiMath 回译、屏幕阅读器 aria-label 片段，以及 KaTeX 渲染预览。
- [CSV 表头别名解析器](https://elysiatools.com/zh/tools/csv-header-alias-resolver): 将杂乱的 CSV 表头映射到干净的目标 schema。粘贴首行为表头的 CSV（列名可能是 Customer ID、user_id、customerId、CUST_ID……），并提供目标 schema（每行一列）与可选的 "alias=target" 别名字典。每个源表头经过四层解析——精确匹配、字典别名、规范化（统一大小写/重音/分隔符/驼峰）、模糊编辑距离——在映射表中显示方法与置信度，并给出目标覆盖率与可选的规范化 CSV 导出。
- [ECharts 主题 Token 抽取器](https://elysiatools.com/zh/tools/echarts-theme-token-extractor): 从 ECharts 主题 JSON 抽取设计 token——颜色、数字、字号与字符串——并直接导出到你的设计系统。粘贴一个主题对象（即通过 echarts.init(dom, themeName) 注册的那种），工具遍历每个叶子节点，为每个颜色（可选地将命名色/rgb 规范化为 hex）、间距数字、字号与字符串打标，然后输出干净的 CSS 变量、Tailwind theme.extend 配置、Style Dictionary tokens.json 或 SCSS 变量。在 ECharts 可视化主题与 Figma/CSS/Tailwind 设计 token 之间架桥，无需逐个手抄。
- [邮件签名 HTML 生成器](https://elysiatools.com/zh/tools/email-signature-html-builder): 生成可直接复制粘贴的 HTML 邮件签名，在 Gmail、Outlook 和 Apple Mail 中均能正确显示——支持头像/logo、社交图标（从你的链接自动识别）、主题色、浅色/深色/自动主题，以及使用内联样式的表格化邮件安全布局。复制原始 HTML，直接粘贴到邮箱客户端即可。

## 示例

- [Web Python 图像处理示例](https://elysiatools.com/zh/samples/web-image-processing-python): Web Python 图像处理示例，使用 PIL/Pillow 包括读取、保存、缩放和格式转换
- [Android Java 图像处理示例](https://elysiatools.com/zh/samples/android-image-processing-java): Android Java 图像处理示例，包括图像读取保存、缩放和格式转换
- [Android Kotlin 图像处理示例](https://elysiatools.com/zh/samples/android-image-processing-kotlin): Android Kotlin 图像处理示例，包括图像读取保存、缩放和格式转换
- [Web Rust 图像处理示例](https://elysiatools.com/zh/samples/web-image-processing-rust): Web Rust 图像处理示例，包括图像读取保存、缩放和格式转换