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 に答える