171
правка
Изменения
Нет описания правки
*** Свойство 1 кажется мне очевидным (если мы знаем тот факт, что сумма и произведение полиномов есть полином). Свойства 2 и 3 доказаны по ссылкам на соответствующие сведения (там есть конкретно рассмотрение этих сведений для задач из класса <tex>P</tex>).
**** Мне свойство 1 очевидным не кажется. Особенно какое-нибудь замыкание Клини. Но это несложные факты, поэтому я не прошу полное доказательство.
***** Написал довольно строгое доказательство замкнутости замыкания Клини. Остальные очень простые, смысла их расписывать не вижу.
** Ссылка на определение констекстно-свободных языков в формулировке соответствующей теоремы.
*** Сделал. Заодно и на регулярные языки тоже сделал ссылку.
** «Но, по теореме…» Запятая здесь не нужна. Мне кажется, лучше просто выпилить это «но».
*** Согласен, сделал.
== TODO 2 ==
* В перечислениях в конце каждого пункта ставится либо точка (если пункт — отдельное предложение), либо точка с запятой (если все пункты — это одно баааальшое предложение). Это я про интерпретацию определния <tex>P</tex>.
** Fixed.
* У доказательства замкнутости относительно замыкания Клини проблемы с форматированием: начало имеет отступ в «2 таба», а конец — вообще не имеет отступа. Думаю, что лучше это доказательство выделить в отделиную лемму и оформить соответствующе.
** Done.
* Будем считать, что мы научились ставить ссылки для текста в техе («примечаниями»). Поэтому в предпоследнем абзаце <tex>NP</tex> можно тоже написать нормально в техе.
** Fixed.
* Вставь ссылки на МТ и НМТ. МТ у нас в вики нет, так что эта ссылка — на википедию. Определние НМТ у нас есть.
** Done.
Небольшой комментарий по поводу программ: в первой можно оставить «return p(f(w))»; во второй хочется замены «poses» на «positions».
<s>Grammar nazi</s> [[Участник:Shevchen|Дмитрий Шевченко]] 17:30, 4 июня 2012 (GST)
