|
所在平台: Udemy |
课程主页: https://www.udemy.com/course/automata-theory-building-a-regexp-machine/
课程评论：没有评论
课程名称：自动机理论：正则表达式机器内部探究 课程概述： 本课程是关于状态机这一计算机科学基本概念的深度学习。状态机广泛应用于现代技术，包括用户界面编程（如React）、自动回复系统、词法分析及形式语言理论（即正则表达式机器），并涉及诸如交通信号灯、自动售货机等现实生活中的应用。状态机是计算理论这一更大理论领域的基础，本课程通过实现正则表达式机器的实例来研究自动机理论。 学习这门课程的原因： 大科技公司（如谷歌、Facebook等）在招聘时倾向于找寻了解基本系统、数据结构和算法的工程师，而不仅仅是程序员。本课程旨在培养学生复杂问题解决能力，帮助他们从理论中汲取经验，为其他系统提供可转移的知识。通过实现一个复杂的理论领域（如状态机），学生可以在熟悉的编程语言中获取新知识，同时学习与系统相关的各种数据结构和算法。 适合人群： 本课程适合任何希望获得有限自动机和正则表达式通用知识的有好奇心的工程师。学员需要具备一定的正则表达式使用经验，课程主要关注如何实现正则表达式，而非如何使用它。此外，词法分析（特别是NFA和DFA）是解析器理论的重要基础，编译器工程师的学习之路可以从有限自动机和词法分析器开始。 课程特色： - 内容简明扼要，每节课都是自成一体，专注于相关主题，不偏离。 - 结合动画演示与实时编辑笔记，帮助学生更容易理解复杂内容，相较于静态幻灯片效果更佳。 课程内容： 课程共分为三部分，包括16节课，涵盖多个子主题。 第一部分：形式文法与自动机 探讨状态机和正则表达式的历史，学习语言理论中的形式文法，并了解不同类型的有限自动机，区分NFA、ε-NFA和DFA。 第二部分：正则表达式NFA片段 关注正则表达式自动机的主要NFA片段，学习如何通过通用组合原则构建复杂机器及其优化。 第三部分：正则表达式机器 实现正则表达式的实际测试方法，理解NFA接受器的工作原理，将其转化为NFA表和DFA表，并详细讲解DFA最小化算法。 希望大家喜欢这门课程，欢迎在评论区讨论问题和建议。 真诚的， Dmitry Soshnikov
Course overviewState machines - the fundamental concept used today in many practical applications, starting from UI programming like React, automated reply systems, lexical analysis in parsers and formal language theory - i.e. the RegExp machines, - and up to real life use cases, such as simple traffic lights, vending machines, and others.The state machines are backed by the larger theoretical field of computer science known as Theory of Computation, and also by its direct theoretical model - the Automata Theory.In this class we study the Automata Theory on the practical example of implementing a Regular Expressions machine.Why to take this class?It's not a secret, that big tech companies, such as Google, Facebook, etc. organize their recruiting process around generalist engineers, which understand basic fundamental systems, data structures, and algorithms. In fact, it's a known issue in tech-recruiting: there are a lot of "programmers", but not so many "engineers". And what does define an "engineer" in this case? - an ability so solve complex problems, with understanding (and experience) in those generic concepts.And there is a simple trick how you can gain a great experience with transferable knowledge to other systems. - You take some complex theoretical field, which might not (yet) be related to your main job, and implement it in a language you're familiar with. And while you build it, you learn all the different data structures and algorithms, which accommodate this system. It should specifically be something generic (for example, State machines), so you can further transfer this knowledge to your "day-to-day" job.In this class we take this approach. To study Automata "Theory" we make it more practical: we take one of its widely-used applications, the lexical analysis, and pattern matching, and build a RegExp machine.Not only we'll completely understand how the Regular Expressions work under the hood (and what will make their usage more professional), but also will be able to apply this knowledge about formal grammars, languages, finite automata - NFAs, DFAs, etc - in other fields of our work.Who this class is for?For any curious engineer willing to gain a generic knowledge about Finite Automata and Regular Expressions.Notice though, that this class is not about how to use regular expressions (you should already know what a regular expression is, and actively use it on practice as a prerequisite for this class), but rather about how to implement the regular expressions - again with the goal to study generic complex system.In addition, the lexical analysis (NFAs and DFAs specifically) is the basis for the parsers theory. So if you want to understand how parsers work (and more specifically, their Tokenizer or "Lexer" module), you can start here too. The path for a compiler engineer starts exactly from the Finite automata and lexical analyzer.What are the features of this class?The main features of these lectures are:Concise and straight to the point. Each lecture is self-contained, concise, and describes information directly related to the topic, not distracting on unrelated materials or talks.Animated presentation combined with live-editing notes. This makes understanding of the topics easier, and shows how (and when at time) the object structures are connected. Static slides simply don't work for a complex content!What is in the course?The course is divided into three parts, in total of 16 lectures, and many sub-topics in each lecture. Below is the table of contents and curriculum.Part 1: Formal grammars and AutomataIn this part we discuss the history of State machines, and Regular expressions, talk about Formal grammars in Language theory. We also consider different types of Finite automata, understanding the differences between NFA, ε-NFA, and DFA.Part 2: RegExp NFA fragmentsIn this part we focus on the main NFA fragments, the basic building blocks used in RegExp automata. We study how by using generic principle of composition, we can obtain very complex machines, and also to optimize them.Part 3: RegExp machineFinally, we implement an actual test method of regular expressions which transit from state to state, matching a string. First we understand how an NFA acceptor works by traversing the graph. Then we transform it into an NFA table, and eventually to a DFA table. We also talk and describe in detail DFA minimization algorithm.I hope you'll enjoy the class, and will be glad to discuss any questions and suggestion in comments.Sincerely,Dmitry Soshnikov
