自动机

A rust 库，用于模拟多种不同的自动机和算法。在其当前形式中包括以下自动机

• 确定有限自动机 (DFA)
• 具有 ε 转移的非确定有限自动机 (NFA)

可视化与调试

cargo run --bin test

包含一个导出到流行 dot 格式的导出器。一个独立的测试二进制文件也展示了构造和使用导出器示例自动机的示例，并立即显示图像。这通过调用 dot（转换为 png）和 feh（渲染图像）来处理，所以请确保安装了这些以获得最佳效果。

注意：所有权转移

此软件包最近的所有权已从 gsingh93 转移，并现在根据大学课程进行维护。理论问题的补充材料可能作为文档的一部分出现。

测试

cargo test

所有单元都通过自动单元测试进行了测试，比它们的接口要求更为严格。这包括自动机构造、语言识别、词拒绝和导出器。

特性

• Dfa
  • 单词成员测试
  • 自动机配对
• Nfa
  • 单词成员（动态幂集）
  • 转换为正则表达式
  • 转换为 DFA
• 正则表达式
  • 在通用字母表上的构造与打印
  • 目前没有特别有趣的内容

待办事项

计划中还有更多功能正在开发中

• 转换器 - 所有 (dfa、nfa、regex) 都是等效的
  • Dfa -> Nfa
  • 正则表达式 -> Nfa
  • 正则表达式 -> Dfa（直接，没有确定步骤）
• 连接、组合、交集、差集、等价性检查
• 最小化
  • 商（Hopcroft）
  • 对偶化、Brzozowski 算法，也许。
• 有限状态转换器 - 及其组合
  • 连接、前缀、后缀
  • 会员资格，投影
  • Presburger算术，使用有限自动机建模线性整数（不等式）的解
• 有限长度语言
  • 最小化
  • 从NFA构建
  • 投影，连接，前缀，后缀
• 决策图
  • 交集，补集
  • 最小化
• 无限词自动机
  • Büchi，Co-Büchi
  • NBA，正则表达式
  • DBA
  • Muller
  • Rabin
  • Streett
  • 奇偶性
• 无限自动机上的算法
  • 并集，交集
  • 补集
  • 空集
  • Emerson-Lei（活力）
• 二阶逻辑
  • 有限词
  • 无限宇宙