状态机( 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

也许你会有兴趣

 欢迎使用e-mail订阅 Soft & Share 

发表评论

Powered by WordPress.com.

Up ↑

%d 博主赞过: