实验1——正规式与状态图 实验目的：编程实现正规式转换到非确定有穷自动机转换的一般算法

1. 实验原理

正规式是表示一类字符串的一种简单方式，可以通过正规式转换为等价的非确定有穷自动机。非确定有穷自动机（NFA）是一种自动机模型，其中转移函数将一个状态和一个输入符号映射到零个或多个状态。NFA与确定有穷自动机（DFA）不同之处在于，DFA每次只能转移一个状态，而NFA可以同时转移多个状态，因此NFA更加灵活，但也更加复杂。

正规式可以通过正则文法转换为等价的非确定有穷自动机。正则文法是一种用于描述正规式的文法，可以通过一系列的规则将正规式转换为等价的正则文法，然后将正则文法转换为等价的NFA。

2. 实验步骤

（1）输入正规式

首先，需要输入一个正规式，例如：a\*b+c。可以使用字符串来表示正规式。

（2）将正规式转换为等价的正则文法

使用正则文法可以描述正规式。可以使用一系列的规则将正规式转换为等价的正则文法，例如：

规则1：将正规式中的+转换为|，例如：a+b+c转换为a|b|c。

规则2：将正规式中的*转换为正则文法中的S->S*|ε，例如：a*b*c转换为S->aSb|ε。

（3）将正则文法转换为等价的非确定有穷自动机

可以使用一般算法将正则文法转换为等价的非确定有穷自动机。该算法的大致步骤如下：

步骤1：构造一个开始状态和一个结束状态。

步骤2：对于正则文法中的每个产生式，为其构造一个转移函数，并将其添加到转移函数集合中。

步骤3：对于每个非终结符，为其添加一个ε转移函数，将其转移到所有可以经过一次ε转移到达的状态。

步骤4：对于每个状态，将其经过ε转移能够到达的所有状态进行合并，形成新的状态。

步骤5：重复步骤4，直到没有新的状态产生。

步骤6：删除所有不可达的状态。

步骤7：得到最终的NFA。

（4）输出状态图

最后，可以将得到的NFA输出为状态图，以便更直观地观察其状态转移过程。

3. 实验结果

输入正规式a\*b+c，得到等价的正则文法为：

S -> aSb | c

将正则文法转换为等价的NFA，得到状态图如下：


4. 实验结论

本实验通过编程实现了正规式转换到非确定有穷自动机转换的一般算法，得到了正规式a\*b+c对应的等价的NFA，并将其输出为状态图。该NFA可以用于匹配符合该正规式的字符串。