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.
138
|
第 4 章
多大的運算能力？
我們在本章遇到了運算能力的兩個新層級：DPDA 比 DFA 和 NFA 更強大，而 NPDA
又更強大。存取堆疊似乎讓下推自動機比有限自動機更多了一點運算能力和複雜性。
擁有堆疊最大的結果是能識別有限自動機不能識別的某些語言的能力，例如回文和對稱
括號字串。堆疊提供的無限儲存讓 PDA 在運算期間能記住任意數量的資訊，並可在稍
後又再參照它。
和有限自動機不同的是，PDA 無需讀取任何輸入即可無限循環，即使不是特別有用，
也讓人覺得好奇。DFA 甚至只能使用輸入的字元來改變狀態，而且儘管 NFA 遵循自由
移動即可自行改變狀態，但是它只能在它結束返回它開始之前才進行有限的次數。另一
方面，PDA 可以處於單一狀態，不僅持續不斷將字元推入堆疊，而且也從未重複相同
的組態。
只想加入運算能力
|
139
下推自動機也可以在有限的程度上控制自己。規則和堆疊之間有個反應迴圈（堆疊的內
容會影響機器可以遵循的規則，而遵循規則將會影響堆疊內容），這允許 PDA 在將會影
響其未來執行的堆疊另外儲存資訊。有限自動機在它們的規則和目前狀態之間依賴類似
的反應迴圈，但是此反應的能力較小，因為當它改變時，會完全忘記目前狀態，而將字
元推入堆疊，保留舊的內容供後續使用。
好吧，所以 PDA
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.