PDA：如何檢查pop是偶數還是奇數

假設我們有上下文無關語言L = {0^n0^n，n> = 0}。PDA：如何檢查pop是偶數還是奇數

對於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

最後的字符串不應該被接受。我無法弄清楚如何在識別字符串之前檢查彈出的數量以選擇是否接受它。有沒有人有任何想法，任何線索來觸發我？

來源

2012-11-10 gon1332

解決方案很簡單。在這種情況下，PDA必須接受偶數個0，包括0的零數。

爲了實現一個簡單的實現是從堆棧中的每個偶數0外觀成立時彈出符號I，所以δ功能是：

___________________________________________________________________ 
    |   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-29 11:05:45 gon1332

PDA：如何檢查pop是偶數還是奇數

回答

相關問題