在下推自动机中以相反的顺序推送/弹出堆栈

所以我正在研究我已经提出的下推自动机和无上下文语言的测试,我坚持这个结构.

我让这个自动机的每个部分都完全正常工作,除了我将在下面解释的一个部分.

它需要识别的语言是:{x#y#z#w | x,y,z,w在{0,1} +中,其中x≠w且y≠z}.

所以我遇到的问题是将Xi与Wi进行比较,因为Wi的元素在自动机处理W时是不知道的,就像我设计的那样.

如果我存储X的内容,当弹出时间并将每个元素与W的元素进行比较时,它们将以相反的顺序弹出,因此认为000111和111000是相同的字符串,而PDA将拒绝,当它应该明确接受(它们是不同的字符串).这只是一个例子,这也会导致错误地分析其他输入.

如果有一种方法可以按相反的顺序将X的内容压入堆栈,它们将以原始形式弹出,这样我就可以正确地比较字符串的内容.

如果在正常推送后有一种方法可以反转堆栈的内容,这也可以让我得出解决方案.

任何帮助将不胜感激.谢谢.

解决方案有点棘手.

实际上没有办法在PDA中反转堆栈的内容.这完全是关于npda的非确定性特性,这使得这个问题可以解决.

从这个更简单的版本开始

L = {x#w: x,w in {0,1}+ and x?w}.

解:

从状态q开始.推$对于x的每一个字母直到第k个字母(K并不重要,选择k不确定性),然后检查k个信去Q0,如果它是0还是去Q1,如果它是1.忽略x的其余部分,直到达到#.为w的每个字母弹出一个$,直到到达堆栈的底部(比如z).检查w的第k个字母.如果[你是在q0并且字母不是0 ]或[你在q1并且字母不是1 ]接受.

就是这样,巫术!