自動機理論：RegExp 機器內部

深入研究狀態機( state machines )、有限自動機( Finite automata )和正規表示式原理

從這 2 小時的課程，你會學到

運算理論
狀態機( State machines ) / 有限自動機 ( Finite automata )
NFA 和 DFA
自動機理論
建立一個完整的 RegExp 機器
圖形( Graphs )，遍歷( traversal )，狀態和轉換( transitions )

要求

基本資料結構和演算法知識
Graphs, trees, traversal 等知識

課程說明

課程概覽

狀態機( state machines )—- 如今在許多實際應用中使用的基本概念，從 UI 程式設計如 React、自動回覆系統、詞法分析解析器和正式語言理論—- 到真實生活中的範例，如簡單的交通號誌、自動販賣機等。

這些狀態機得到了電腦科學這個更大的理論領域的支援，這個領域被稱為運算理論( Theory of Computation )，同時也得到了它的直接理論模型—- 自動機理論( Automata Theory )。

在本課程中，我們將以實現正規表示式機器( Regular Expressions machine )的範例來學習自動機理論。

為什麼要上這門課？

大型科技公司，比如 Google ，Facebook 等，圍繞通才工程師來組織他們的招聘流程，這已經不是什麼祕密了，通才工程師瞭解基本的系統，資料結構和演算法。事實上，這是技術招聘中的一個眾所周知的問題: 有很多“程式設計師” ，但沒有那麼多“工程師”。在這種情況下“工程師”的定義是什麼？ー解決複雜問題的能力，對一般概念有理解(和經驗)。

還有一個簡單的技巧，你可以通過將知識轉移到其它系統來獲得豐富的經驗。ー選擇一些可能與你的主要工作無關的複雜理論領域，用你熟悉的語言來實現它。當你建立它的時候，你學習了所有不同的資料結構和演算法，這些都適用於這個系統。它應該是通用的(例如，State machines) ，這樣你就可以將這些知識進一步轉移到你的“日常”工作中。

在這門課中，我們採用這種方法。為了研究自動機“理論” ，我們使它更加實用: 我們使用它的一個廣泛使用的應用—- 詞法分析( lexical analysis )和模式匹配，並建立一個 RegExp 機器。

我們不僅能夠完全理解正規表示式( Regular Expressions )的工作原理(以及如何使它們的使用更專業) ，而且還能夠將形式語法、語言、有限自動機ー NFAa、 DFAs 等方面的知識應用到我們工作的其它領域。

這門課是給誰上的？

對於任何好奇的工程師，希望獲得有限自動機和正規表示式的通用知識。

不過請注意，這個課程不是關於如何使用正規表示式(你應該已經知道什麼是正規表示式，並且在實務中積極使用它作為這個課程的先決條件) ，而是關於如何實現正規表示式ー再次以研究通用複雜系統為目標。

此外，詞法分析( 特別是 NFAs 和 DFAs )是解析器理論的基礎。因此，如果你想了解解析器是如何運作的(更具體地說，是它們的 Tokenizer 或“ Lexer”模組) ，你也可以從這裡開始。編譯器( compiler ) 工程師的路徑完全從有限自動機和詞法分析器開始。

這門課的特色是什麼？

這些講座的主要特點是:

簡明扼要，直奔主題。每個講座都是自成一體的，簡潔明瞭，並且描述了與主題直接相關的資訊，而不是對不相關的材料或談話分散注意力。

動畫簡報結合現場編輯筆記。這使得理解主題更加容易，並顯示如何(以及何時)連接物件結構。靜態的簡報根本不適用於複雜的內容！

課程內容是什麼？

本課程共分為三個部分，共16堂課，每堂課有多個副主題。下面是目錄和課程表。

第一部分: 形式語法( Formal grammars )與自動機

在這一部分我們討論了狀態機的歷史，正規表示式，討論了語言理論中的形式語法。我們還考慮了不同類型的有限自動機，瞭解 NFA 與 -NFA 和 DFA 的區別。

第二部分: RegExp NFA 片段

在這一部分中，我們將重點介紹主要的 NFA 片段，這是 RegExp 自動機中使用的基本建構區塊。我們研究如何利用通用的組合原理，可以得到非常複雜的機器，並對它們進行最佳化。

第三部分: RegExp 機器

最後，我們實現了正規表示式從一個狀態轉換到另一個狀態，匹配一個字串的實際測試方法。首先，我們通過遍歷圖表( traversing the graph )來了解 NFA 接受者是如何工作的。然後我們將其轉換為 NFA 表，並最終轉換為 DFA 表。我們還討論並詳細描述了有限自動機的最小化 / 值演算法。

我希望你們能喜歡這堂課，並樂於在評論中討論任何問題和建議。

Sincerely,

Dmitry Soshnikov

目標受眾

任何願意處理一個複雜的專案，建立一個基於有限自動機 RegExp 機器的好奇的工程師都

講師簡介

Dmitry Soshnikov Facebook 軟體工程師

Dmitry Soshnikov 是一名軟體工程師，也是一名有不同於電腦科學主題的講師。

他對教育充滿熱情，注重高品質的教育內容: 簡明扼要，並使用現場編輯筆記的動畫講座。

你會從 Dimitry 的課程學到:

編譯器和直譯器: 建立一個程式語言
垃圾收集器(自動記憶體管理)
程式設計語言理論
自動機理論: 建立一個 RegExp 機器
解析器理論: 實現一個編譯器編譯程式

英文字幕：有

想要了解如何將英文字幕自動翻譯成中文? 請參考這篇 How-To

點選 ✨ 資料科學機器學習課程 NT320 起的優惠連結 ( 優惠不限於資料科學機器學習課程，需登入 Udemy 取得)| Udemy 永久擁有課程 ( 在電腦瀏覽器登入，點選“優惠連結”後再回想要的課程介紹中點選“報名參加課程”即可取得）
Udemy 現在越來越多課程有中文字幕，請參考 Soft & Share 中文線上課程
手機上點選優惠連結看到的價格比電腦上看到的貴
＄代表當地貨幣, 如在台灣為 NT
點選”報名參加課程”有可能因瀏覽器 cookies 轉久一點或回報錯誤而無法連上，請稍等刷新或重新點選就會出現