2

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

我如何把它变成一个等效的下推自动机

4

1 回答 1

3

下推自动机可以将符号推送到堆栈顶部并将它们弹出。它还可以将其转换基于最顶部的堆栈符号。我们需要考虑一种机制，允许我们通过操作堆栈来接受正确的语言。

您的语法生成的语言具有以下特征：

  1. 它22在中间
  2. 这是一个回文结束{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。基本上，在我们读取任何 substring 之后22，我们必须猜测该实例是否22是中间的那个。如果是这样，我们需要开始读取初始字符串以查看是否有回文。如果没有，我们需要继续将符号压入堆栈。

于 2017-05-01T14:39:16.083 回答