Изменения
→Соотношение классов Reg и P
{{Теорема
|statement =
Класс [[Регулярные языки: два определения и их эквивалентность|регулярных языков]] входит в класс <tex>\mathrm{P}</tex>, то есть: <tex>\mathrm{Reg } \subset \mathrm{P}</tex>.
|proof =
<tex>\mathrm{Reg } \subset \mathrm{TS}(n, 1) \subset \mathrm{P}</tex>''Замечание.'' <tex>\mathrm{TS}</tex> {{---}} ограничение и по времени, и по памяти.
}}
