November 2017
Beginner to intermediate
344 pages
7h 2m
Chinese
Content preview from 深入理解運算原理｜從簡單的機器到無所不能的程式
Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
O’Reilly covers everything we've got, with content to help us build a world-class technology community, upgrade the capabilities and competencies of our teams, and improve overall team performance as well as their engagement.I wanted to learn C and C++, but it didn't click for me until I picked up an O'Reilly book. When I went on the O’Reilly platform, I was astonished to find all the books there, plus live events and sandboxes so you could play around with the technology.I’ve been on the O’Reilly platform for more than eight years. I use a couple of learning platforms, but I'm on O'Reilly more than anybody else. When you're there, you start learning. I'm never disappointed.I'm always learning. So when I got on to O'Reilly, I was like a kid in a candy store. There are playlists. There are answers. There's on-demand training. It's worth its weight in gold, in terms of what it allows me to do.
只想加入運算能力
|
113
決定論下推自動機
利用資料在計算時可以獲得保存的專屬臨時空間來擴充有限狀態機，就能解決儲存空間
的問題。除了以它的狀態提供有限的內部記憶體，這個空間還提供機器一種外部記憶
體，我們將會發現，擁有外部記憶體會讓機器的計算能力大大不同。
儲存空間
將儲存空間加到有限自動機的簡單方式，是讓它存取一種稱為
堆疊
（
stack
）的後進先
出資料結構：字元會被推進這種資料結構，然後再從中提出字元。堆疊雖然是一種簡單
且有限制的資料結構（只有頂端的字元能隨時存取），我們必須捨棄頂端字元才能找出
在它之下的字元為何，而只要我們將一串字元推入堆疊，就只能以相反的順序提出它
們），但是它的確妥善處理了儲存空間有限的問題。堆疊大小沒有內建的限制，因此原
則上它可以增長以儲存所需要的資料量
4
。
內建堆疊的有限狀態機稱為
下推自動機
（
pushdown automaton
，PDA），且若該機器的規
則是決定論，就稱之為
決定論下推自動機
（
deterministic pushdown automaton
，DPDA）。
能夠存取堆疊其實開啟了新的可能性；舉例來說，這就很容易設計可識別括號對稱字串
的 DPDA。以下是它的運作方式：
• 將兩種狀態提供給這部機器，1 和 2，而狀態 1 是接受狀態。
• 讓機器從空堆疊、狀態 1 開始運作。
• 處於狀態 1 且讀取起始括號時，將一些字元推入堆疊（讓我們使用代表『括號』
[bracket] 的
b
），並移入狀態 2。
• 處於狀態 2 且讀取起始括號時，將字元
b
推入堆疊。 ...
Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
and much more.
Read now
Unlock full access
More than 5,000 organizations count on O’Reilly
O’Reilly covers everything we've got, with content to help us build a world-class technology community, upgrade the capabilities and competencies of our teams, and improve overall team performance as well as their engagement.Julian F.
I wanted to learn C and C++, but it didn't click for me until I picked up an O'Reilly book. When I went on the O’Reilly platform, I was astonished to find all the books there, plus live events and sandboxes so you could play around with the technology.Addison B.
I’ve been on the O’Reilly platform for more than eight years. I use a couple of learning platforms, but I'm on O'Reilly more than anybody else. When you're there, you start learning. I'm never disappointed.Amir M.
I'm always learning. So when I got on to O'Reilly, I was like a kid in a candy store. There are playlists. There are answers. There's on-demand training. It's worth its weight in gold, in terms of what it allows me to do.