Jay*_*ayB 5 automata non-deterministic pushdown-automaton automata-theory
所以我正在研究我已经提出的下推自动机和无上下文语言的测试,我坚持这个结构.
我让这个自动机的每个部分都完全正常工作,除了我将在下面解释的一个部分.
它需要识别的语言是:{x#y#z#w | x,y,z,w在{0,1} +中,其中x≠w且y≠z}.
所以我遇到的问题是将Xi与Wi进行比较,因为Wi的元素在自动机处理W时是不知道的,就像我设计的那样.
如果我存储X的内容,当弹出时间并将每个元素与W的元素进行比较时,它们将以相反的顺序弹出,因此认为000111和111000是相同的字符串,而PDA将拒绝,当它应该明确接受(它们是不同的字符串).这只是一个例子,这也会导致错误地分析其他输入.
如果有一种方法可以按相反的顺序将X的内容压入堆栈,它们将以原始形式弹出,这样我就可以正确地比较字符串的内容.
如果在正常推送后有一种方法可以反转堆栈的内容,这也可以让我得出解决方案.
任何帮助将不胜感激.谢谢.
小智 6
解决方案有点棘手.
实际上没有办法在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 ]接受.
就是这样,巫术!