Теория автоматов и формальных языков (ФКН, напр. ПрИнж; Попова А. Е.)

Теория автоматов и формальных языков составляет математическую основу многих алгоритмов работы с текстами, в том числе поиска слов в тексте, а также процедур лексического и синтаксического анализа, реализуемых при компиляции программных кодов. В курсе описаны два взаимодополняющих способа формализации понятия языка -- порождающие грамматики и автоматы. Большое внимание уделяется самым распространённым типам грамматик -- регулярным и контекстно-свободным, а также рассматриваются основы синтаксического анализа.