fbpx

狀態機( State machines ) 和自動機 ( Automata ) : 建立一個 RegExp 機器

課程簡介

深入研究狀態機、有限自動機和 正規表示式 原理

課程介紹:English 简中

從這 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 的課程學到:

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

英文字幕:有

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

優惠資訊

如何購買這門課程比較划算?可以參考課程合購優惠方案


報名參加課程

Sponsored by Udemy

也許你會有興趣

 學習資訊不漏接-歡迎使用 App 訂閱發文通知 

發表迴響

這個網站採用 Akismet 服務減少垃圾留言。進一步瞭解 Akismet 如何處理網站訪客的留言資料

Powered by WordPress.com.

Up ↑

%d 位部落客按了讚: