State Machines and Automata: Building a RegExp Machine

Preview this course

State machines—the fundamental concept used today in many practical applications, starting from UI programming such as React, automated reply systems, lexical analysis in parsers, and formal language theory. In this course, we will study the automata theory on the practical example of implementing a regular expressions machine.

Unlimited access to 750+ courses.
Enjoy a Free Trial. Cancel Anytime.

- OR -

30-Day Money-Back Guarantee
Full Lifetime Access.
24 on-demand videos & exercises
Level: All Levels
English
1hrs 47mins
Access on mobile, web and TV

What to know about this course

It’s not a secret that big tech companies, such as Google, Facebook, and others, organize their recruiting process around generalist engineers who 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 to solve complex problems, with understanding (and experience) in those generic concepts.  And there is a simple trick how you can gain 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 that accommodate this system. It should specifically be something generic (for example, state machines) so that you can further transfer this knowledge to your “day-to-day” job.  In this course, 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.

Who's this course for?

This course is mainly for compiler engineers. However, all curious engineers willing to tackle a complex project building a RegExp machine based on finite automata would find it useful. Notice 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 systems.

What you'll learn

  • Learn about the theory of computation.
  • Learn about state machines and finite automata.
  • Learn about graphs, traversal, states, and transitions.
  • Learn how to build a full RegExp machine.
  • Learn about non-deterministic and deterministic finite automata.
  • Learn about formal grammar and finite automata.

Key Features

  • Learn about RegExp history and regular grammars.
  • Learn about character and epsilon NFA fragments.
  • Learn about NFA acceptor and NFA table.

Course Curriculum

About the Author

Dmitry Soshnikov

Dmitry Soshnikov is a software engineer and a lecturer on different computer science topics. He is passionate about education and focuses on high-quality educational content: concise and straight-to-the-point animated lectures with live-editing notes.. Dmitry Soshnikov is a software engineer and a lecturer on different computer science topics. He is passionate about education and focuses on high-quality educational content: concise and straight-to-the-point animated lectures with live-editing notes.