实验1：正则表达式与有限自动机的理解与实现

"实验1-正则表达式与有限自动机1" 实验1的主要目标是深化理解正则表达式、非确定有限自动机（NFA）和确定有限自动机（DFA）及其识别的语言。实验内容包括设计DFA的数据结构和存储格式、验证DFA的正确性、实现能列出所有长度小于等于给定整数N的字符串的功能，以及判断一个字符串是否为DFA所能识别的规则字符串。 1. **DFA的数据结构与存储** DFA通常由五元组表示：(Q, Σ, δ, q0, F)，其中Q是状态集合，Σ是输入符号集，δ是状态转移函数，q0是初始状态，F是终止状态集合。在实验中，选择数组来存储DFA的状态转换图。由于普通数组不能直接存储字符，可以将字符集存储在一个数组e中，字符在e中的索引代表其在DFA中的位置。 2. **DFA正确性检查** 这部分涉及确保DFA五元组的正确性。检查始态和终态是否在状态集合Q内，且不大于最大状态；所有转移都指向有效的状态，并且转移的字符属于字母表；同时防止重复填写同一个DFA项目的不同值导致错误。 3. **识别长度小于等于N的字符串** 实现这一功能需要使用深度优先搜索（DFS）策略。从初始状态开始，根据输入字符在字母表的位置进行递归搜索。当搜索到的字符串长度超过N时，返回上一层继续搜索其他路径。此过程会输出所有长度小于等于N的可识别字符串。 4. **字符串识别** 字符串识别通过模拟DFA的运行过程完成。从初始状态开始，逐个字符地检查DFA的状态转移。如果在DFA存储数组中找不到对应状态和字符的转移，表示识别失败。如果成功遍历整个字符串并到达终止状态，则识别成功。 5. **设计问题与对策** 在实现过程中可能遇到的问题包括递归搜索的逻辑错误，这需要正确设置递归结束条件。此外，字母表的存储最初考虑使用map，但考虑到遍历不便，改为普通数组。在字符串识别时，需额外判断识别完字符串后，当前状态是否为终止状态，避免错误判断。 这个实验提供了实践经验，帮助学生深入理解正则表达式和有限自动机的理论知识，并锻炼了他们在实际编程中解决问题的能力。