pushdown-automaton - 卡在下推自动机上

Question

我被困在一个PDA问题上。问题如下：

求以下语言的下推自动机： L={xcy : x, y ∈ (a+b)*, y is not the reverse of x, c is literal}

我已经构建了以下机器：http: //i.imgur.com/EPeofGA.jpg

我的机器不接受xc形式的字符串（其中 y 是空字符串），或xcy 形式的任何字符串，|y| < |x|, y 不是 x 的反转。

当输入结束时，我需要让机器从 q1 转换到 q2 ，但堆栈不是空的......但是添加从 q1 到 q2 的空输入转换会导致我的机器接受所有形式的字符串xcy，无论是否y 是 x 的反转。

任何见解都值得赞赏。

Answer 1

一个真正的脑筋急转弯，因为“纯”PDA 无法明确匹配输入的结尾。

只有空输入转换可供您使用，您需要将空输入转换（堆栈顶部除了 Z 之外的任何东西）指向一个新的接受状态 q3，它不可能有进一步的转换；每当有更多输入要读取时，非确定性将使 q3 成为无关紧要的副业，而当 q1 到达输入末尾且堆栈中仍有内容时，它会成为接受路径。

编辑： JFLAP 中的此修改：