形式语言jflap操作创建第一个有穷自动机.docx
《形式语言jflap操作创建第一个有穷自动机.docx》由会员分享，可在线阅读，更多相关《形式语言jflap操作创建第一个有穷自动机.docx（20页珍藏版）》请在冰点文库上搜索。
形式语言jflap操作创建第一个有穷自动机
创建第一个有穷自动机
定义
JFLAP中定义一个有穷自动机M,M是个五元组M =（Q,Σ,δ, qs, F），其中：
Q 是一个有穷的状态集合{qi | i 是个非负整数}
Σ是有穷的输入字母表
δ是转换函数,δ:
D → 2Q ， D 是 Q × Σ*中的有穷子集
qs （是Q中的一个元素）是初始状态
F （是Q的一个子集）是终态集合
注意，这样的定义包含了确定有穷自动机（DFAs），稍后我们就会讨论到，还有包含了非确定有穷自动机（NFAs）。
在JFLAP中新建各类自动机大体上都是相似的，让我们先从新建一个DFA来描述语言
L ={ambn :
m ≥ 0,n> 0, n 是奇数}
我们将要创建一个DFA来识别一个由若干个a和奇数b组成的语言。
（例子来源于SusanRodger和ThomasFinley写的JFLAP:
AnInteractiveFormalLanguagesandAutomataPackage中）
编辑窗口
为了创建一个新的有穷自动机，先打开JFLAP，然后从菜单中点击FiniteAutomaton选项
然后将出现一个允许我们创建和编辑有穷自动机的新窗口。
编辑窗口被分成两个部分：
可将自动机构造在上面的编辑窗口，还有创建自动机需要的工具栏。
编辑窗口
让我们来近距离看看工具栏：
如你所见，工具栏上有如下四个工具：
+属性编辑工具
：
设置初始状态和终态
+状态创建工具
：
创建状态
+转移创建工具
：
创建转移
+删除工具
：
删除状态和转移
当要选择工具的时候，直接左击相应的图标即可。
当选择好工具后，相应的图标会变暗。
现在让我们开始创建我们的有穷自动机。
创建状态
首先，让我们创建一个状态。
在工具栏上点击
按钮，然后在编辑窗口上不同区域左击来创建状态。
我们不确定我们需要多少状态，先创建4个状态。
编辑窗口类似下图：
已经创建的状态
定义初试状态和终态
我们直接定义q0为我们的初试状态。
选择工具栏中的
，右击q0，如下图所示
在弹出的菜单中，选择Initial，这样做好后，在q0后会出现一个白色的箭头标记为初试状态。
同样的，右击q1，选择Final，q1所在的圆会变成同心圆，标记为终态。
现在，我们定义好了初态和终态，下面我们来创建转移函数。
创建转移函数
在我们的例子中，L语言必须是以a开头，所以初态必须含有a的转移。
同时，例子中，a的数目是不限的，这就意味着在输入若干个a后，我们的有穷自动机依然是相同的状态，即，输出函数是q0指向q0自己。
为了创建这样一个转移函数，先选择转移函数工具
，然后在编辑窗口上点击q0，在q0上会出现一个文本框：
这个λ，代表空字符串（空转换），默认填写在文本框里。
当然，如果想要ε代表空转换，在菜单里选择Preferences:
Preferences来选择符号表示空字符串。
输入a，然后按回车。
如果文本框没有出现，那就按Tab去选择他，然后输入a。
输入好后，可以看到的界面类似下图：
接下来，我们知道，在L语言中必须以奇数个b结束。
同时，我们知道转移函数里的从q0接受的b必须是终态。
选择转移函数创建工具
，然后创建初态q0到终态q1的转移函数，按住q0不放，拖到q1上松开鼠标，像之前输入转移函数a那样输入b。
那么，两个状态之间的转移函数如下图所示：
最后，我们知道我们的语言接受奇数个b结尾的字符串，为了达到这个目的，有两种方法：
回到q0，然后再回到q1，或者引入一个新的状态，转到到这个新状态q2，再回到q1。
第一种方法不可取，因为这个方法不光接受我们所要的字符串，还接受abbab这样的错误字符串。
因此，我们引入一个新的状态q2。
创建一个在q1接受b到q2的转移函数。
这样，我们的有穷状态机就完整了，来看看吧：
你可能注意到q3状态是没有实际作用的，接下来，我们将要介绍怎么删除状态和转移函数。
删除状态和转移函数
为了删除q3，先选择删除工具
，然后点击状态q3，你的编辑窗口会类似下图：
相似的，删除转移函数的时候，在删除状态下点击输入字符即可。
这样，我们的有穷自动机，jaex.jff，完成了。
运行有穷自动机
现在，我们完成了有穷自动机，我们可以试试这个语言能不能接受相应的字符串。
为了做到这一点，在菜单栏上选择Input:
MultipleRun
一个新的标签页如下图所示：
点击Input列里的第一行输入字符串，按回车键继续输入下一个字符串。
当输入完成后，点击RunInputs来测试我们的自动机能否接受我们所输入的字符串。
在Result一栏里会显示Accept或者Reject。
我们还可以直接点击LoadInputs按钮选择已经输入好字符串的测试文件。
点击Clear删除所有的输入字符串，点击ViewTrace会弹出一个新窗口显示选择输入的转换轨迹，如果想返回编辑窗口，在菜单栏中选择File:
DismissTab。
创建一个非确定有穷自动机
构造NFA和DFA是非常相似的。
NFA与DFA不同的是，它会满足多个条件之中的一个。
首先，如果一个有穷自动机有两个从同一个状态接受相同的字符的转移函数，这就是NFA。
其次，如果一个有穷自动机中有一个或者多个转移函数中接受空字符串，那这也是个NFA。
让我们看看ex1.3a.jff这个NFA的例子。
我们可以直接认为这个NFA，因为从q3到q9有四个空转换，但是我们不能确定我们已经发现所有的不确定的状态，JFLAP可以帮助我们完成它。
强调不确定性状态
在菜单拦选择Test:
HighlightNondeterminism可以查看NFA里的所有不确定状态。
将会出现一个新的便签页，其中不确定的状态被标注为深颜色的。
如图所示，q3和q9的确是不确定的状态，以为他们的接受有空转换，同时我们还注意到q1也是不确定状态，因为他有两个接受相同字符的转移函数a。
NFA的输入测试
选择菜单栏中的Input:
StepwithClosure，将会弹出一个对话框，供我们输入。
通常我们直接输入我们想要测试的字符串就好了，同时我们还可以输入选择文件来输入字符串。
注意：
当我们选择从文件输入字符串的时候，JFLAP将通过空格来判断是否为字符串结束。
将会在窗口最前端出现一个新标签页，在该标签页下方，有组合面板，同时当前的状态会标注为阴影。
首先，我们来看看组合选项：
在组合一栏的左上角，我们可以看到当前的状态的相关详情。
文本框里的字符串当中
已经处理了的字符显示为灰色。
点击来Step处理下一个字符的输入，我们会发现q1状态变暗了。
再次点击Step去处理下一个a，你会发现四个状态都变灰了。
由于这个自动机是非确定的。
从q1，都有接受a并且到q2，q9的转换。
由于q9有两个空转换，这个NFA可以用两种组合进行转换。
这样，模拟器现在拥有四种组合。
点击Step处理下一个字符。
注意在上图中，有两个组合被注明红色高亮，这意味着他们是不合格的，观察输入，我们知道只有输入aa是接受的。
发生了什么呢？
产生跟踪
点击选择一个组合，选择好后，这个组合颜色会变深，再次点击可取消选择。
点击在q11有冲突的组合，并点击Trace，将会出现一个新的窗口，将会显示该组合的回溯：
从上图中，我们可以看到该组合从q0开始，并且处理了第一个a后转移到q1，然后处理了第二个a后，转移到q11。
尽管q11与q1不是相邻的，但是他可以从q9通过空转换到达。
当这个模拟器尝试处理接下来的a时，可以发现从q11没有接受a的转移，在这里发生了冲突。
尽管有冲突的组合将会在下一步中被移除，我们同样可以移除不冲突的组合。
移除组合
观察有冲突组合的轨迹，我们会发现在q11和q6状态下，接受字符a都会被拒绝。
点击选择四个组合，再点击Remove，模拟器将不会继续模拟这些组合。
如下图所示：
观察上图的两个组合，我们意识到q3状态将不会出现可接受的组合，我们可以暂停其他的组合来测试我们的想法。
暂停和恢复组合
点击选择q10所在组合，然后点击Freeze，可以暂停该组合。
当一个组合被暂停之后，将会显示为暗紫色。
当q3所在组合暂停后，点击Step该组合将保持原样。
多次点击Step后，将会发现q3所在组合同样不会接受其他的。
如下图所示：
选择组后后，点击Thaw，恢复该组合。
现在模拟器将会想平常那样一步步的接受输入。
多次点击Step之后，将会发现有一个可以接受的组合，该组合将会被标记成绿色：
如果我们此时再次点击Step，我们将会看到最后一个组合将会被拒绝，同时，仅有一个可接受的组合。
然后，我们不确定这是否是真正的实例，因为我们起初了一些组合，我们可以重置模拟器再次检查其他的。
重置模拟器
任何时候，我们可以点击Reset来重置模拟器，这将会清除当前所有组合，并重启模拟器。
如果我们重置模拟器并一步步测试所有的组合，我们将会发现的确有一个可接受的组合。
附录
说明
我们可以选择属性编辑器，然后右击并选择“AddNote”，来对JFLAP文件添加注释。
注释默认为"insert_text"。
点击这个注释，并输入我们想要输入的。
注释好后，可以点击和拖拽相应注释。
选择
选择属性编辑器，点击空白处，然后拖拽鼠标，这样我们可以一次性选择多个状态。
选择好后会出现一个矩形，矩形内的所有被选择的状态将会显示成绿色，可以拖拽矩形里的任意一个状态，来移动所有的状态。
点击其他地方，可以取消选择。
布局命令
我们可以使用JFLAP预定义的布局样式来使我们的图表更美观。
升级会员 