Automata Theory: inside a RegExp machine

1h 48m 5s
English
Paid

Course description

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.

Read more about the course

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!

Watch Online

This is a demo lesson (10:00 remaining)

You can watch up to 10 minutes for free. Subscribe to unlock all 16 lessons in this course and access 10,000+ hours of premium content across all courses.

View Pricing

Watch Online Automata Theory: inside a RegExp machine

0:00
/
#1: RegExp history

All Course Lessons (16)

#Lesson TitleDurationAccess
1
RegExp history Demo
05:09
2
Regular grammars
09:32
3
Finite automata
09:09
4
Character and Epsilon NFA
07:09
5
Concatenation pattern: AB
06:42
6
Union pattern: A|B
06:53
7
Kleene closure: A*
06:04
8
Complex machines
04:33
9
Syntactic sugar
03:30
10
NFA optimizations
04:48
11
NFA acceptor
05:19
12
NFA table
08:17
13
RegExp-Tree tool
04:53
14
DFA table
09:45
15
DFA minimization
10:59
16
RegExp match
05:23

Unlock unlimited learning

Get instant access to all 15 lessons in this course, plus thousands of other premium courses. One subscription, unlimited knowledge.

Learn more about subscription

Comments

0 comments

Want to join the conversation?

Sign in to comment

Similar courses

Deployment from Scratch

Deployment from Scratch

Sources: Josef Strzibny
"Deployment from Scratch" is an introduction to web application deployment that covers the entire process from basic concepts to complex server and database...
AI For Developers With GitHub Copilot, Cursor AI & ChatGPT

AI For Developers With GitHub Copilot, Cursor AI & ChatGPT

Sources: Academind Pro
This course is designed for developers who want to use AI effectively! AI is not a threat, but a powerful tool capable of making you even more...
4 hours 55 minutes 24 seconds
Bedrock: Jumpstart your next SaaS product

Bedrock: Jumpstart your next SaaS product

Sources: Max Stoiber (@mxstbr)
The modern full-stack Next.js & GraphQL boilerplate with user authentication, subscription payments, teams, invitations, emails and everything else you need.
Introduction to RAG

Introduction to RAG

Sources: DAIR.AI
This course is dedicated to creating efficient and reliable applications based on Retrieval-Augmented Generation (RAG). Students will learn the main...
2 hours 23 minutes 5 seconds
Supercharged Code Editing with Vim and Neovim

Supercharged Code Editing with Vim and Neovim

Sources: zerotomastery.io
Enhance your coding skills with easy-to-learn Vim and Neovim techniques. Use them in IDEs and terminals to boost productivity and navigate code swiftly.
2 hours 55 minutes 8 seconds