对于上下文无关语法，我如何将其转换为等效的下推自动机？
For a context free grammar, how do i convert it to an equivalent push down automaton?
对于 Σ = {0, 1, 2} 上的上下文无关文法 G，起始变量 S：
S → 0S0 | 1S1 | 2S2 | Y
Y → 22
如何将其转换为等效的下推自动机
下推自动机可以将符号压入堆栈顶部并将其弹出。它还可以将其转换基于最顶层的堆栈符号。我们需要考虑一种机制，允许我们通过操纵堆栈来接受正确的语言。
您的语法生成的语言具有以下特征：
- 中间有
22
- 它是
{0, 1, 2} 的回文。也就是说，它向前读取与向后读取相同。
我们需要 "remember" 字符串的开头，以便我们能够判断字符串的结尾是否向后重复。这是堆栈的一个很好的用例：我们可以在看到符号时将它们压入堆栈，然后在我们读回它们时将它们弹出。另一个注意事项：我们知道我们只能在阅读 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 的那个实例是否是中间的那个。如果是这样，我们需要开始回读初始字符串以查看是否有回文。如果不是，我们需要继续将符号压入堆栈。
对于 Σ = {0, 1, 2} 上的上下文无关文法 G，起始变量 S：
S → 0S0 | 1S1 | 2S2 | Y
Y → 22
如何将其转换为等效的下推自动机
下推自动机可以将符号压入堆栈顶部并将其弹出。它还可以将其转换基于最顶层的堆栈符号。我们需要考虑一种机制，允许我们通过操纵堆栈来接受正确的语言。
您的语法生成的语言具有以下特征：
- 中间有
22 - 它是
{0, 1, 2}的回文。也就是说，它向前读取与向后读取相同。
我们需要 "remember" 字符串的开头，以便我们能够判断字符串的结尾是否向后重复。这是堆栈的一个很好的用例：我们可以在看到符号时将它们压入堆栈，然后在我们读回它们时将它们弹出。另一个注意事项：我们知道我们只能在阅读 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 的那个实例是否是中间的那个。如果是这样，我们需要开始回读初始字符串以查看是否有回文。如果不是，我们需要继续将符号压入堆栈。