BuptLab_FLA_nfa2dfa

本仓库是北京邮电大学《形式语言与自动机》实验一：NFA到DFA的转化的作业仓库。

项目简介

该项目是北京邮电大学《形式语言与自动机》课程的实验一：NFA到DFA的转化实现。本项目通过图形用户界面实现了不确定有限自动机(NFA)到确定有限自动机(DFA)的自动转换，并提供了可视化绘制功能。

文件结构

BuptLab_FLA_nfa2dfa/
├── README.md                # 项目说明文档
├── requirements.txt         # 项目依赖
├── setup.py                 # 打包工具
├── docs/                    # 文档目录
│   └── FLA_Lab_1.md         # 实验要求文档
├── src/                     # 源代码目录
│   ├── algorithms/          # 算法实现
│   │   ├── nfa2dfa.py       # NFA到DFA转换算法
│   ├── gui/                 # 图形界面相关
│   │   ├── drawer.py        # 绘图工具
│   │   └── mainwindow.py    # 主窗口实现
│   └── structures/          # 数据结构定义
│       ├── NFA.py           # NFA类定义
│       └── DFA.py           # DFA类定义

功能特点

• 通过图形用户界面定义NFA的各个组成部分（状态集合、字母表、转移函数、初态、终态）
• 使用子集构造法自动将NFA转换为DFA
• 可视化绘制NFA和DFA状态转移图
• 打印DFA状态转移表

使用说明

您可以从我们的Release页面下载最新版本的可执行程序，也可以通过以下方式运行：

通过源码运行

1. 运行程序：

   python src/gui/mainwindow.py
   

2. 定义NFA：

   • 点击"状态集合"按钮输入所有状态（以空格分隔）
   • 点击"字母表"按钮输入所有输入符号（以空格分隔）
   • 点击"转移函数"按钮在弹出窗口中定义状态转移
   • 点击"初态"按钮输入初始状态
   • 点击"终态"按钮输入终止状态集合（以空格分隔）

3. 转换与可视化：

   • 点击"转换"按钮将NFA转换为DFA
   • 点击"绘制NFA"查看NFA状态转移图
   • 点击"绘制DFA"查看DFA状态转移图
   • 点击"打印DFA状态转移表"查看转换后的DFA状态转移表

创建可执行文件

如果需要自行构建可执行文件，请按照以下步骤操作：

1. 安装必要的依赖：

   pip install -r requirements.txt
   

2. 执行构建命令：

   python setup.py build
   

3. 获取可执行文件： 构建完成后，运行可执行文件

技术实现

• 使用Python作为主要编程语言
• Tkinter库实现图形用户界面
• 采用子集构造法（Subset Construction）算法实现NFA到DFA的转换
• 利用Canvas组件实现自动机状态图的绘制

许可证

本项目遵循学术使用规范