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.
126
|
第 4 章
=> true
>> dpda_design.accepts?('abmb')
=> false
>> dpda_design.accepts?('baambaa')
=> false
這雖然很棒，但在輸入字串中間的
m
卻是逃避的藉口。為什麼我們不能設計一個只需要
識別回文（
aa
、
abba
、
babbaabbab
等等）的機器，而不必標記中間點？
機器只要到達字串的中間點，就必須從狀態 1 變更到狀態 2，但若沒有標記，它無法知
道何時要執行這件工作。如同我們之前看到的 NFA，這些『我怎麼知道何時該 ... ？』
的問題，只要放寬決定論的限制並允許機器能在任何時刻變更重要狀態就可以解決，因
此只要在正確的時間遵循正確的規則，它就可能接受回文。
沒有決定論限制的下推自動機就稱為
非決定論下推自動機
（
nondeterministic pushdown
automaton
），這一點都不讓人意外。以下是個利用偶數個字母識別回文的例子
6
：
這幾乎和 DPDA 版本相同，不同之處是讓狀態 1 移到狀態 2 的規則：它們在 DPDA 從
輸入讀取
m
，但在這裡它們則是自由移動。這給了 NPDA 機會，讓 NPDA 不需標記即
可在輸入字串時的任何地方改變狀態。
模擬物
非決定論機器比決定論機器更難模擬，但是我們已經在第 74 頁的『非決定論』完成了
NFA 的艱苦工作，因此可以將相同的概念重複用在 NPDA。我們需要
NPDARulebook
來
保存非決定論的
PDARules
諸多規則，它的實作物和
NFARulebook ...
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.