设计一个 PDA，其中包含所有非 ww^R 形式的 0 和 1 字符串
Design a PDA of all strings of 0's and 1's that are not of the form ww^R
我必须创建一个 PDA（下推自动机），它接受 not 形式的字符串。
例如它接受 0011、1100、11000 但不接受 1001、011110、0110。
我如何创建这个PDA？我知道不接受 ww 的答案，但无法获得洞察力来制作这个。
如果你能告诉我答案或好的提示，我将不胜感激。
要接受 ww^R，您将 w 的符号压入堆栈，不确定地猜测您已到达 w 的末尾，然后读取 w^R，同时从堆栈弹出匹配符号。这可能接受的唯一方法是如果你的猜测是正确的，那么它只会接受你的字符串的形式是否正确。
要接受不是 ww^R 形式的所有内容，请考虑以下内容：
首先，非确定性地猜测输入长度的奇偶性。如果您猜测输入的长度为奇数，并且您是对的，那么它是该语言中的一个字符串，因为奇数长度的字符串不能是 ww^R 的形式。这样做可以让我们将另一个分支集中在不符合要求形式的偶数长度字符串的情况下。
非 ww^R 形式的偶数长度字符串的定义特征是对于从 1 到 |w| 的至少一个索引 k，确实 x[k] 不是等于 x[2|w|-k+1]。因此，我们可以将 w 压入堆栈，就像 ww^R 的 PDA 一样；并且我们可以不确定地猜测我们已经以相同的方式到达了 w 的结尾。然而，我们不要求输入符号等于栈顶符号，而是为任何输入符号弹出一个堆栈符号，并且我们将进一步要求至少一个输入符号与其对应的栈顶符号不匹配 -堆栈符号。我们可以通过为弹出阶段设置两个状态来做到这一点：第一个对应于没有遇到至少一个不匹配，第二个对应于已经看到一个或多个不匹配。最后，如果我们处于这些状态中的第二种，没有进一步的输入符号和空堆栈，我们可以接受。
我必须创建一个 PDA（下推自动机），它接受 not
例如它接受 0011、1100、11000 但不接受 1001、011110、0110。
我如何创建这个PDA？我知道不接受 ww 的答案，但无法获得洞察力来制作这个。
如果你能告诉我答案或好的提示，我将不胜感激。
要接受 ww^R，您将 w 的符号压入堆栈，不确定地猜测您已到达 w 的末尾，然后读取 w^R，同时从堆栈弹出匹配符号。这可能接受的唯一方法是如果你的猜测是正确的，那么它只会接受你的字符串的形式是否正确。
要接受不是 ww^R 形式的所有内容，请考虑以下内容：
首先，非确定性地猜测输入长度的奇偶性。如果您猜测输入的长度为奇数，并且您是对的，那么它是该语言中的一个字符串，因为奇数长度的字符串不能是 ww^R 的形式。这样做可以让我们将另一个分支集中在不符合要求形式的偶数长度字符串的情况下。
非 ww^R 形式的偶数长度字符串的定义特征是对于从 1 到 |w| 的至少一个索引 k，确实 x[k] 不是等于 x[2|w|-k+1]。因此，我们可以将 w 压入堆栈，就像 ww^R 的 PDA 一样；并且我们可以不确定地猜测我们已经以相同的方式到达了 w 的结尾。然而，我们不要求输入符号等于栈顶符号，而是为任何输入符号弹出一个堆栈符号，并且我们将进一步要求至少一个输入符号与其对应的栈顶符号不匹配 -堆栈符号。我们可以通过为弹出阶段设置两个状态来做到这一点：第一个对应于没有遇到至少一个不匹配，第二个对应于已经看到一个或多个不匹配。最后，如果我们处于这些状态中的第二种，没有进一步的输入符号和空堆栈，我们可以接受。