Udemy
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
Development
Web Development Data Science Mobile Development Programming Languages Game Development Database Design & Development Software Testing Software Engineering Development Tools No-Code Development
Business
Entrepreneurship Communications Management Sales Business Strategy Operations Project Management Business Law Business Analytics & Intelligence Human Resources Industry E-Commerce Media Real Estate Other Business
Finance & Accounting
Accounting & Bookkeeping Compliance Cryptocurrency & Blockchain Economics Finance Finance Cert & Exam Prep Financial Modeling & Analysis Investing & Trading Money Management Tools Taxes Other Finance & Accounting
IT & Software
IT Certification Network & Security Hardware Operating Systems Other IT & Software
Office Productivity
Microsoft Apple Google SAP Oracle Other Office Productivity
Personal Development
Personal Transformation Personal Productivity Leadership Career Development Parenting & Relationships Happiness Esoteric Practices Religion & Spirituality Personal Brand Building Creativity Influence Self Esteem & Confidence Stress Management Memory & Study Skills Motivation Other Personal Development
Design
Web Design Graphic Design & Illustration Design Tools User Experience Design Game Design Design Thinking 3D & Animation Fashion Design Architectural Design Interior Design Other Design
Marketing
Digital Marketing Search Engine Optimization Social Media Marketing Branding Marketing Fundamentals Marketing Analytics & Automation Public Relations Advertising Video & Mobile Marketing Content Marketing Growth Hacking Affiliate Marketing Product Marketing Other Marketing
Lifestyle
Arts & Crafts Beauty & Makeup Esoteric Practices Food & Beverage Gaming Home Improvement Pet Care & Training Travel Other Lifestyle
Photography & Video
Digital Photography Photography Portrait Photography Photography Tools Commercial Photography Video Design Other Photography & Video
Health & Fitness
Fitness General Health Sports Nutrition Yoga Mental Health Dieting Self Defense Safety & First Aid Dance Meditation Other Health & Fitness
Music
Instruments Music Production Music Fundamentals Vocal Music Techniques Music Software Other Music
Teaching & Academics
Engineering Humanities Math Science Online Education Social Science Language Teacher Training Test Prep Other Teaching & Academics
AWS Certification Microsoft Certification AWS Certified Solutions Architect - Associate AWS Certified Cloud Practitioner CompTIA A+ Cisco CCNA Amazon AWS CompTIA Security+ AWS Certified Developer - Associate
Graphic Design Photoshop Adobe Illustrator Drawing Digital Painting InDesign Character Design Canva Figure Drawing
Life Coach Training Neuro-Linguistic Programming Personal Development Mindfulness Meditation Personal Transformation Life Purpose Emotional Intelligence Neuroscience
Web Development JavaScript React CSS Angular PHP WordPress Node.Js Python
Google Flutter Android Development iOS Development Swift React Native Dart Programming Language Mobile Development Kotlin SwiftUI
Digital Marketing Google Ads (Adwords) Social Media Marketing Google Ads (AdWords) Certification Marketing Strategy Internet Marketing YouTube Marketing Email Marketing Google Analytics
SQL Microsoft Power BI Tableau Business Analysis Business Intelligence MySQL Data Modeling Data Analysis Big Data
Business Fundamentals Entrepreneurship Fundamentals Business Strategy Online Business Business Plan Startup Blogging Freelancing Home Business
Unity Game Development Fundamentals Unreal Engine C# 3D Game Development C++ 2D Game Development Unreal Engine Blueprints Blender
30-Day Money-Back Guarantee
Development Programming Languages Computer Science

State machines and Automata: building a RegExp machine

Deep dive into state machines, Finite automata, and Regular expressions
Highest Rated
Rating: 4.7 out of 54.7 (43 ratings)
1,994 students
Created by Dmitry Soshnikov
Last updated 7/2019
English
English
30-Day Money-Back Guarantee

What you'll learn

  • Theory of Computation
  • State machines / Finite automata
  • NFA and DFA
  • Automata Theory
  • Build a full RegExp machine
  • Graphs, traversal, states and transitions

Course content

3 sections • 16 lectures • 1h 47m total length

  • Preview05:08
  • Regular grammars
    09:31
  • Finite automata
    09:08

  • Preview07:08
  • Concatenation pattern: AB
    06:41
  • Union pattern: A|B
    06:52
  • Kleene closure: A*
    06:03
  • Complex machines
    04:32
  • Syntactic sugar
    03:29
  • NFA optimizations
    04:47

  • NFA acceptor
    05:18
  • NFA table
    08:16
  • Preview04:52
  • DFA table
    09:44
  • DFA minimization
    10:58
  • RegExp match
    05:22

Requirements

  • Basic data structures and algorithms
  • Graphs, trees, traversal

Description

Course overview

State 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 Automata

In 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 fragments

In 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 machine

Finally, 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

Who this course is for:

  • Any curious engineer willing to tackle a complex project building a RegExp machine based on Finite automata

Instructor

Dmitry Soshnikov
Software engineer and Instructor
Dmitry Soshnikov
  • 4.8 Instructor Rating
  • 253 Reviews
  • 3,028 Students
  • 5 Courses

Dmitry Soshnikov is a Software engineer, and a lecturer on different computer science topics.

He is passioned about education, and focuses on high-quality educational content: concise and straight to the point animated lectures with live-editing notes.

You will learn:

- Compilers and interpreters: building a Programing language

- Garbage Collectors (Automatic memory management)

- Theory of programming languages

- Automata Theory: Building a RegExp machine

- Parsers theory: Implementing a Parser Generator

  • Udemy for Business
  • Teach on Udemy
  • Get the app
  • About us
  • Contact us
  • Careers
  • Blog
  • Help and Support
  • Affiliate
  • Impressum Kontakt
  • Terms
  • Privacy policy
  • Cookie settings
  • Sitemap
  • Featured courses
Udemy
© 2021 Udemy, Inc.