C# 中的确定性有限自动机类

• 下载源代码 - 1.33 KB

引言

上述可下载的 zip 文件仅包含一个小的 C# 类，它是确定性有限自动机 (DFA) 的一个简单实现。我在大学的理论计算机科学课程中遇到了这个问题，并且发现能够实际测试所有那些仅在纸上构造的 DFA 非常有用。

背景

对于那些不了解的人来说，DFA 是正则语言概念背后的理论机器模型；特别是，DFA 等价于正则表达式。有关完整介绍，请参阅此 Wiki 文章。

Using the Code

只需将该类添加到现有项目中即可。

一个简单的 DFA 示例，用于正则语言 PARITY，它是所有具有奇数个 1 的二进制字符串的语言，如下所示：f 是接受状态的集合，delta 是转移矩阵（也称为状态转移表，有关此矩阵结构的更多说明，请参阅代码中的注释），M 是我们由此定义的 DFA。在 for 循环中，执行一些统计测试：DFA 类包含一个 static RandomString 方法，此处用于生成长度为 10 的二进制字符串。

然后，假设您可以使用一个名为 ArrayToString 的方法（该方法应返回一个 string），则输出随机 string ，然后是 DFA M 是否接受此 string 的信息。

 int[] f = new int[] { 1 };
 int[,] delta = new int[,] { { 0, 1 }, { 1, 0 } };

 DFA M = new DFA(delta, f);
 int[] s;

 for (int i = 0; i < 10; i++)
 {
     s = DFA.RandomString(10, 2);
    textBox1.AppendText(ArrayToString(s) + " - " 
    + M.Accepts(s).ToString() + System.Environment.Newline);
 } 

关注点

下一步可以执行的操作是对此类自动机进行图形显示，但这似乎需要一个多小时的工作……

历史

• 2007 年 5 月 31 日：初始发布