GATE | GATE-IT-2004 |问题40

以下哪个字符串不是 A. 成员 L（M）？

（A） aaa （B） 阿巴布 （C） 巴巴 （D） 巴布 答复: （C） 说明： 掌上电脑基础知识 A. 下推自动机 或者PDA本质上是一个带有堆栈的NFA，其转换功能也取决于堆栈顶部的符号。形式上，PDA是一个6元组（Q，∑，Γ，δ，q0，F），其中Q是所有可能状态的集合，∑是所有可能输入的集合，Γ是所有可能堆栈符号的集合，δ：Q∑×Γ→ Q×Γ是过渡函数，q0是初始状态，和 F⊆ Q是最终状态的集合。

有时，当我们将初始堆栈符号z0视为 超过6个元组。请注意，对于给定的输入，应该存在一个转换函数，否则将不会有任何可能的移动。

PDA可以有两种类型：空堆栈接收PDA和最终状态PDA。

空堆栈接受PDA是指在给定输入字符串上接受给定输入的PDA，当输入耗尽时，堆栈应为空。

类似地，接受PDA的最终状态是一种PDA，如果在给定的输入字符串上，当输入耗尽时，PDA应处于最终状态之一，则该PDA接受给定的输入。

非确定性PDA或NPDA是一种PDA，其中对于给定的输入，多个输出是可能的。i、 e.转移函数δ将给定的输入从Q∑xΓ映射到有限的Q×Γ集。 对于给定的问题 由于有一个以上的输出对应于一个给定的转换函数输入，所以我们将考虑一个NPDA来执行输入，如果一个给定的输入没有可能的移动，我们将停止相应的分支的执行，我们假设如果机器在最后一个状态之一停止并且输入被耗尽，我们接受字符串，否则拒绝它。注意，给定的PDA是接受PDA的最终状态，而不是接受PDA的空堆栈。

问题的选择：

我们假设初始堆栈符号为ε，并且

• 在选项1中 ，执行如下： （s，a，）→ （s，a）或（f，ε）。 让我们首先考虑，（s，a）作为输出并执行剩余的输入。（s，a，a）→ 没有有效的行动。 停下这根树枝 而不是最终状态，所以不被接受。现在考虑（f，ε）作为输出。（f，a，ε）→ 没有有效的行动。 停下这根树枝 请注意，PDA处于最终状态之一，但输入字符串未用尽，因此PDA不应接受该状态。 • 在选项2中 ，执行将从选项1开始，并在角色2停止，因为无法移动。与第一个选项不一样，也不接受该选项。 3.

• 选择3 ，执行如下： （s，b，ε）→ （s，a）。（s，a，a）→ 没有可能的行动。 停下这根树枝 .由于在到达任何最终状态之前停止，因此此选项不被接受。

• 选择4 ，此选项也不被接受，因为PDA将在第二个字符处停止，就像它在前一个选项中停止一样。此选项也不被接受。

假设如果PDA由于无法移动而停止输入，并且当前状态是最终状态之一，但输入未用尽，PDA将拒绝该字符串，对于问题2，每个答案都是正确的，即给定的For字符串都不属于给定PDA的语言。

同样，假设PDA由于无法移动而停止输入，并且如果当前状态是最终状态之一，但输入未耗尽，PDA将继续使用输入字符串，直到字符串结束，选项（a）和选项（B）中的字符串将被该PDA的语言接受。而选项（C）和选项（D）最终仍不会被接受 对于字符串，PDA不会处于最终状态。所以记住这个假设，选项（C）和选项（D）对于这个问题都是正确的。

这一解释是由 德格什·潘迪。 这个问题的小测验