http://neerc.ifmo.ru/wiki/api.php?action=feedcontributions&feedformat=atom&user=94.25.229.17&* 2026-06-13T21:21:37Z Вклад участника MediaWiki 1.30.0 http://neerc.ifmo.ru/wiki/index.php?title=%D0%A3%D1%87%D0%B0%D1%81%D1%82%D0%BD%D0%B8%D0%BA:Dgerasimov/%D0%A2%D0%B8%D0%BA%D0%B5%D1%82%D1%8B_%D0%BF%D0%BE_%D0%BA%D0%BE%D0%BD%D1%81%D0%BF%D0%B5%D0%BA%D1%82%D0%B0%D0%BC_year2011&diff=33120 2013-10-16T18:17:17Z

<p>94.25.229.17: /* Автоматы и регулярные языки */ баг</p> <hr /> <div>== Автоматы и регулярные языки ==<br /> # '''!!!''' [[Основные определения: алфавит, слово, язык, конкатенация, свободный моноид слов; операции над языками]]<br /> ## Добавить сюда определение гомоморфизма, образа и прообраза в соответствующий раздел, взять их [[Замкнутость регулярных языков относительно различных операций|отсюда]], оттуда соответственно, удалить их определения и сослаться на этот конспект. Еще лучше — создать <br /> ## В конспекте упоминается &quot;свободный моноид&quot;, но не написано что это такое. Надо написать (в конспекте про моноид), и написать про то, какие еще бывают моноиды (кажется, это называется &quot;моноид с порождающими соотношениями&quot;, но, может, говорят и &quot;несвободный моноид&quot;), поищите.<br /> ## Добавить английские аналоги терминам<br /> # '''!!!''' [[Регулярные языки: два определения и их эквивалентность]]<br /> ## Множества языков (вроде Reg, и Reg') тут зачем-то пишутся курсивом, что вообще не принято, их всегда обозначают большими прямыми (возможно, жирными) буквами. '''Короче, везде надо использовать для классов языков \mathrm!'''<br /> ## Множества вроде R_i тоже следует обозначать большими прмямыми буквами, так как они перепутываются с языками L, M и т.п.) <br /> ## Мне кажется, первое определение — это по сути означает множество языков, представимое регулярными выражениями, думаю, надо это упомянуть. P.S. Более того, если я не ошибаюсь, кажется, вообще в конспектах нигде нет определения регулярных выражений, так что это определение по сути им является.<br /> ## &lt;tex&gt;\bigcap\limits_{R - nadreg}&lt;/tex&gt;, вот это nadreg выглядит совершенно мерзко, надо от него избавиться. Возможно, найти/придумать разумный английский термин и писать под объединением что-то вроде R is X, где X — это название, которое вы найдется или придумаете.<br /> # [[Детерминированные конечные автоматы]]<br /> # [[Прямое произведение ДКА]]<br /> ## Английские термины<br /> ## Добавить ссылку на факт про эквивалентность автоматных и регулярных<br /> # [[Недетерминированные конечные автоматы]]<br /> ## Английские термины<br /> # [[Построение по НКА эквивалентного ДКА, алгоритм Томпсона]]<br /> # [[Автоматы с eps-переходами. Eps-замыкание]]<br /> # [[Теорема Клини (совпадение классов автоматных и регулярных языков)]]<br /> ## Опять классы языков курсивом<br /> # [[Замкнутость регулярных языков относительно различных операций]]<br /> #: см. 1<br /> # [[Анализ свойств регулярных языков (пустота, совпадение, включение, конечность, подсчет числа слов)]]<br /> ## &lt;tex&gt;paths&lt;/tex&gt; выглядит мерзко, такие штуки надо оборачивать в какой-нибудь \mathrm<br /> # [[Интерпретация булевых формул с кванторами как игр для двух игроков]]<br /> #: вообще левая штука, относящаяся скорее к логике. Наверное, надо вообще выпилить это из списка конспектов по автоматам и сделать ссылку из леммы о накачке (оно для нее, видимо, и рассказывалось)<br /> # '''!!!''' [[Доказательство нерегулярности языков: лемма о разрастании]]<br /> ## пофиксить неправильное доказательство. Точнее, может, оно и правильное, но не нужно, так как не показывает пример нерегулярного языка, для которого лемма о накачке выполняется.<br /> ## добавить ссылок на англоязычные источники, добавить в статью англоязычные термины <br /> # [[Решение уравнений в регулярных выражениях]]<br /> # '''!!!''' [[Альтернативное доказательство теоремы Клини (через систему уравнений в регулярных выражениях)]]<br /> #: фиг знает что это, но надо написать, видимо<br /> # [[Эквивалентность состояний ДКА]]<br /> # [[Минимизация ДКА, алгоритм за O(n^2) с построением пар различимых состояний]]<br /> # [[Минимизация ДКА, алгоритм Хопкрофта (сложность O(n log n))]]<br /> # '''!!!''' [[Контексты и синтаксические моноиды]]<br /> ## добавить английских терминов<br /> ## доказательство последнего утверждения<br /> ## вообще написать что-нибудь еще бы, типа зачем оно вообще надо.</div>

94.25.229.17