Перед началом: Так как образовательная платформа нашего вуза не работает по непонятным мне причинам, я начну с самого конца. Будет много непонятных на первый взгляд определений, но, думаю, суть алгоритма уловить получится. Минимальная теория: Условимся называть Регулярное выражение - РВ. А конечный автомат - КА. Известно, что можно строить разные РВ и для этих РВ существуют свои КА. Существует теоремка как раз про это. Теорема Для любого РВ существует эквивалентный ему КА. ...

Сложно сказать какой процент программистов с ней знаком и ещё сложнее сказать, кто её использует на практике. Помнится, когда мы проходили это в институте и решали малопонятные задачки, казалось, что это как-то абстрактно и далеко от нас...