下推自動機（a^x b a^y c a^x + y）

Question

我的朋友問我一個關於下推自動機的問題。 abacaa。我正在查看一些類似的問題，但所有問題都包含偶數，就像0^a 1^a，但現在我有3個值。我發現an example有關但我不能轉換我的問題。

aabbabcc: 

read a push 1 
read a push 1 
read b pop 1 
read b pop 1 
stack is empty so push 0 
read a push 1 
read b pop 1 
top of stack is 0 so push 0 
read c pop 0 
read c pop 0 

我該如何轉換abacaa？

Answer 1

我知道這已經有一段時間了，但只是爲了防止有人在尋找類似的問題......爲什麼要重新這樣做呢？

其基本思想是：一個下推自動機有一個堆棧。因此，請按照您的意願閱讀儘可能多的a，然後每次將額外的「a」推入堆棧。然後閱讀b並轉到下一個狀態。

現在再次讀取儘可能多的a，將所有a再次推入堆棧。然後閱讀c並轉到下一個狀態。

現在，只要您正在查看堆棧頂部的'a'，就閱讀a。當您查看堆棧底部符號時，轉換到最終接受狀態。

如果你有更多的a，沒有轉換，並且你的字符串不被接受（你沒有閱讀過，而且你沒有去留，所以你「崩潰」了機器）。否則，如果您在以前的狀態中用完了a，則永遠不會使其進入最終狀態，並且您的字符串不被接受。 只有當您剛剛閱讀了與前兩次一樣多的a時，纔會以接受狀態結束，並且沒有更多輸入可供讀取，並且字符串被接受。