对于上下文无关语法，我如何将它转换为等价的下推自动机？

Question

对于Σ= {0,1,2}上的上下文无关文法G，其中起始变量S：
S→0S0 | 1S1 | 2S2 | Ÿ
Ÿ→22

我如何变成一个相当于下推自动机

Answer 1

一个下推自动机可以在堆栈的顶部推符号，弹出他们关闭此。它也可以将其转换置于最上面的堆栈符号上。我们需要考虑一种机制，让我们通过操纵我们的堆栈来接受正确的语言。

你的语法生成的语言，有以下特点：

1. 它在中间
2. 22这是一个回文超过{0, 1, 2}。也就是说，它向后读取相同的向前。

我们需要“记住”字符串的开头，以便我们能够判断字符串的末尾是否向后重复。对于堆栈来说，这是一个很好的用例：我们可以在看到它们时将这些符号推入堆栈，然后在我们读取它们时将它们弹出。另一个说明：我们知道我们只能在阅读22之后尝试开始阅读。

首先，我们读到的一切，把它压入堆栈，直到找到“22”：

Q s S Q' S' 
---------------------- 
// read 0s and 1s and push them on the stack 
q0 0 Z q0 0Z 
q0 0 0 q0 00 
q0 0 1 q0 01 
q0 1 Z q0 1Z 
q0 1 0 q0 10 
q0 1 1 q0 11 

// if you read a 2, pus it on the stack and 
// go to a new state where we look for a second 2 
q0 2 Z q1 2Z 
q0 2 0 q1 20 
q0 2 1 q1 21 

// if you read a 2 and then 0 or 1, go back to the 
// initial state and keep reading input. otherwise, 
// if you find a second two, proceed 
q1 0 2 q0 02 
q1 1 2 q0 12 
q1 2 2 q2 22 

// assume the '22' we just saw was not the one in 
// the middle of the input string and that we need 
// to keep reading input. 
q2 0 2 q0 02 
q2 1 2 q0 12 
q2 2 2 q2 22 

// assume the '22' we just saw was the one in the 
// middle of the input string and that we now need 
// to start reading from the stack. 
q2 - 2 q3 - 
q3 - 2 q4 - 
q4 0 0 q4 - 
q4 1 1 q4 - 
q4 2 2 q4 - 
q4 - Z q5 Z 

// we read a string in the language and are 
// ready to accept in q5. go to dead state q6 
// explicitly if still have input. 
q5 0 Z q6 Z 
q5 1 Z q6 Z 
q5 2 Z q6 Z 

// consume the rest of the input in the dead state. 
q6 0 Z q6 Z 
q6 1 Z q6 Z 
q6 2 Z q6 Z 

的转换为q5和q6不是严格必要的，如果你定义崩溃机器意味着字符串被明确拒绝，这是典型的。我将这些转换包括在内，以便PDA能够优雅地使用所有输入而不会崩溃。

此PDA不确定。这种语言没有确定性的PDA。基本上，在我们读取任何子串22之后，我们必须猜测22的实例是否是中间的一个。如果是这样，我们需要开始阅读最初的字符串，看看我们是否有回文。如果不是，我们需要继续推动堆栈上的符号。