2

假设我们有上下文无关语言 L={0^n0^n, n>=0}。

对于 PDA：Μ = {A, Q, H, δ, q0, h0, F} 我们有：

A = {"0"}
H = {X, I}
Q = {S, T}
q0 = S
h0 = X
F = {T}

Then, the δ function is:
   ___________________________________________________________________
   |           X            |             I            |      -|     |
---+------------------------+--------------------------+-------------|
S  | read("0")=> push(I)    |   read("0")=> push(I)    |             |
   | keep=> move(T)         |   pop                    |             |
---+------------------------+--------------------------+-------------|
T  |                        |                          |   success   |
---------------------------------------------------------------------+

这是我的解决方案，但它有一个问题。自动机必须接受诸如 00、ε、0000 之类的字符串，而不接受 0 或 000。通常接受具有偶数个 0 的字符串。

让我们尝试 2 个示例： 

->for string 00:
 MOVE    STACK    INPUT    STATE    DESCRIPTION_OF_MOVE
  1      X         '0'0      S        reading_of 0
  2      XI          '0'     S        reading_of 0
  3      XII        ε        S        pop
  4      XI         ε        S        pop
  5      X          ε        S        ε-transition
  6      X          ε        T        success

->for string 000:
 MOVE    STACK    INPUT    STATE    DESCRIPTION_OF_MOVE
  1      X        '0'00      S        reading_of 0
  2      XI        '0'0      S        reading_of 0
  3      XII         '0'     S        reading_of 0
  4      XIII       ε        S        pop
  5      XII        ε        S        pop
  6      XI         ε        S        pop
  7      X          ε        S        ε-transition
  8      X          ε        T        success

不应接受最后一个字符串。我不知道如何在识别字符串之前检查弹出次数以选择是否接受它。有没有人有任何想法，有什么线索可以触发我？

4

1 回答 1

0

解决方案很简单。在这种情况下，PDA 必须接受偶数个 0，包括零个 0。

为了实现这一点，一个简单的实现是I每次出现偶数个 0 时从堆栈中弹出符号，因此δ函数将是：

   ___________________________________________________________________
   |           X            |             I            |      -|     |
---+------------------------+--------------------------+-------------|
S  | read("0")=> push(I)    |   read("0")=> pop        |             |
   | keep=> move(T)         |                          |             |
---+------------------------+--------------------------+-------------|
T  |                        |                          |   success   |
---------------------------------------------------------------------+

让我们尝试 2 个示例：

->for string 00:
 MOVE    STACK    INPUT    STATE    DESCRIPTION_OF_MOVE
  1      X         '0'0      S        read(0)=> push(I)
  2      XI          '0'     S        read(0)=> pop
  3      X          ε        S        ε-transition
  4      X          ε        T        success

->for string 000:
 MOVE    STACK    INPUT    STATE    DESCRIPTION_OF_MOVE
  1      X        '0'00      S        read(0)=> push(I)
  2      XI        '0'0      S        read(0)=> pop
  3      X           '0'     S        read(0)=> push(I)
  4      XI         ε        S        eoi=> failure
于 2016-10-29T11:05:45.040 回答