141
правка
Изменения
+ ссылки
{{Теорема
|statement =
Класс [[Регулярные языки: два определения и их эквивалентность|регулярных языков ]] входит в класс <tex>P</tex>, то есть: <tex>Reg \subset P</tex>.
|proof =
<tex>Reg \subset TS(n, 1) \subset P</tex>
{{Теорема
|statement =
Класс [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободных языков ]] входит в класс <tex>P</tex>, то есть: <tex>CFL \subset P</tex>.
|proof =
<tex>CFL \subset TS(n^3, n^2) \subset P</tex>
