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.
74
|
第 3 章
非決定論有限自動機
要瞭解 DFA 並加以實作是一件簡單的事情，但那是因為它們非常類似我們已經熟悉的
機器。在剝離了真實電腦的所有復雜性之後，我們現在有機會嘗試較不常規的想法，讓
我們遠離過去使用的機器，而不必處理隨著這些想法在真實系統運作而來的困難。
其中一種探索的方法是消除我們現有的假設和限制。首先，決定論似乎有其限制：也許
我們不在意每種狀態的每個可能的輸入字元，因此在某些意外發生時，我們為何就不能
忽略我們不在意的字元規則，並且假設該機器可以進入一般的故障狀態？更奇怪的是，
允許機器擁有相互矛盾的規則以便可以擁有一條以上的執行路徑到底意謂著什麼？我們
的方案也假設每個狀態更改都必須發生在從輸入串流讀取字元的回應，但如果該機器勿
需讀取任何字元就可以改變狀態，這會發生什麼事？
我們將在本節研究這些想法，並觀察調整有限自動機的能力會開啟什麼新的可能性。
非決定論
假設我們想要一部只要第 3 個字元是
b
就會接受任何字串
a
和
b
的有限自動機（這裡的
字串 a、b 裡面可以有數個 a 或 b 字元）。這很容易就能提出適合的 DFA 設計：
如果我們想要的機器所接受字串的
倒數第 3 個
字元是
b
，這該怎麼辦？它會如何運作？
似乎更為困難：上述會保證 DFA 在讀取第 3 個字元時會位於狀態 3，但是機器在讀取
倒數第 3 個字元時並無法提前得知，因為它直到讀完字串才知道字串有多長。它可能無
法馬上清楚這樣的 DFA 是否更為可行。
最簡單的電腦
|
75
然而，如果我們放寬決定論限制並允許規則手冊針對給定的狀態和輸入包含多條規則 ...
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.