141
правка
Изменения
+ ещё теоремка
{{Теорема
|statement =
Класс регулярных языков входит в класс <tex>P</tex>, то есть: <tex>Reg \subset P</tex>
|proof =
<tex>Reg \subset TS(n, 1) \subset P</tex>
''Замечание.'' <tex>TS</tex> {{---}} ограничение и по времени и по памяти.
}}
== Соотношение классов <tex>CFL</tex> и <tex>P</tex> ==
{{Теорема
|statement =
Класс контекстно-свободных языков входит в класс <tex>P</tex>, то есть: <tex>CFL \subset P</tex>
|proof =
<tex>CFL \subset TS(n^3, n^2) \subset P</tex>
Первое включение выполняется благодаря существованию [[Алгоритм Эрли|алгоритма Эрли]].
}}
