形式语言jflap操作-创建你的第一个下推自动机

实用文档创建你的第一个下推自动机定义JFLAP定义了一个非确定性的下推自动机(NPDA)M作为七的M=(Q,Σ,Γ,δ,qs,Z,F)

Q是一个有限集合{qi|i是一个非负整数}

Σ是有限的输入字母

Γ是有限的堆栈字母表

δ是转换函数,δ:Q×Σ*×Γ*是Q×Γ*的有限子集

qs(Q的成员)是初始状态

Z是堆栈开始符号(必须是一个大写字母Z)

F(Q的子集)是一组最终状态

注意,这个定义包括确定性下推自动机,它只是不确定的下推自动机的唯一一个可用的路线带如何创建一个自动机对于用于创建一个自动机的许多通用工具、菜单和窗口的知识,应首先阅读有限自动机教程。本教程将主要集中在功能和选项,从有限自动机中来区分下推自动机。我们将开始通过构造一个确定性NPDA语言L={anbn:n>0}。我们的方法是每输入一个“a”则置于堆栈顶部，“b”进栈的时候“a”出栈。开始一个新的NPDA,开始JFLAP并单击下推自动机的选择从菜单,如下所示:

你应该最终看到一个空白的屏幕,看起来像下面的屏幕。有许多相同的按钮、菜单和功能目前存在的有限自动机。然而,有一些差异,我们将很快遇到。

四个状态应该足够来描述语言L={anbn:n>0}。添加四个状态到屏幕上,设置初始状态是q0和终止状态是q3。屏幕应该类似于下面的这个：

现在是时候添加过渡。尝试添加一个q0和q1之间的过渡状态。然而,与那些创建有限自动机相比，这些转换还是有一些不同的。你会注意到,有三个输入,而不是一个。

第一个箱子中的值代表输入处理,在第二个箱子中代表当前值在堆栈的顶部,最后的值代表了新的值被推到堆栈的顶部,将原来的值从顶部推出栈。这里任何一个盒子都没有限制值得大小

现在,是时候添加输入。从默认过渡状态改变,点击第一个框。第一个框，输入一个值“a”，第二个框,输入值“Z”(默认角色的元素在堆栈底部),在第三个框，输入值“aZ”。使用Tab键或鼠标在箱子之间切换,然后按回车键或点击鼠标在屏幕外框完成后。这种转变意味着以下情况。如果第一个符号输入的是“a”,第一个堆栈的元素是“Z”,这台机器的状态是“q0”,然后“Z”出栈,并且将“aZ”压入堆栈。这种转变从而增加了一个“a”,如果利用堆栈。当完成时,区域之间q0和q1应该类似于下面的例子。

让我们完成转换。添加一个过渡(a,a;aa)在q1之间并且q1完成了an部分。在q1和q2之间创建转换(b,a;λ)并且q2和q2之间代表bn部分。最后,在q2和q3之间的(λ,Z,Z)将允许输入到达最终状态。完成后,屏幕看起来应该像这样:

为了您的方便,我们创建的NPDA在pdaexample.jff中是可用的。现在,单击“输入”菜单并选择“步骤与闭合“。将会提示你输入,所以进入“aaaabbbb”(表示a4b4)。在点击“OK”或按enter,下面的屏幕将出现:

这非常类似于相应的屏幕自动装置。然而,一位显著的区别在于,在第二个框中的文本面板的左下角。目前包含一个“Z的这个文本框”是我们的堆栈。如果我们单击步骤按钮,我们可以看到一个示例,说明了模拟运行时栈的变化。现在是一个“a”在“Z”的前面。当我们继续模拟运行,当an被处理的时候，堆栈将是其最大值，但不是任何bn值。然而,随着b值进行处理,它将变得越来越小。堆栈将最后回到开始,值为“Z”。因此我们完成我们的第一个确定性NPDA。不确定的NPDAs

不确定的NPDAs以类似的方式工作。下面一个例子是,一个可以访问在线这里here。

以下是一个模拟的“输入→一步步关闭”以字符串“aabb”为例:

StartStep1Step2

现在是当非确定性开始断言本身,并且自动机可以不止一个路径。最后一步包含了程序可能携带的所有的排序可能，但只有一个路径最后成功。

Step3

Ste