Участник:Dgerasimov/Тикеты по конспектам year2011 — различия между версиями
(→Автоматы и регулярные языки) |
(→Автоматы и регулярные языки) |
||
| Строка 1: | Строка 1: | ||
== Автоматы и регулярные языки == | == Автоматы и регулярные языки == | ||
| − | # [[Основные определения: алфавит, слово, язык, конкатенация, свободный моноид слов; операции над языками]] | + | # '''!!!''' [[Основные определения: алфавит, слово, язык, конкатенация, свободный моноид слов; операции над языками]] |
## Добавить сюда определение гомоморфизма, образа и прообраза в соответствующий раздел, взять их [[Замкнутость регулярных языков относительно различных операций|отсюда]], оттуда соответственно, удалить их определения и сослаться на этот конспект. Еще лучше — создать | ## Добавить сюда определение гомоморфизма, образа и прообраза в соответствующий раздел, взять их [[Замкнутость регулярных языков относительно различных операций|отсюда]], оттуда соответственно, удалить их определения и сослаться на этот конспект. Еще лучше — создать | ||
| − | ## В конспекте упоминается "свободный моноид", но не написано что это такое. Надо написать (в конспекте про моноид), и написать про то, какие еще бывают моноиды (кажется, это называется "моноид с порождающими соотношениями", но, может, говорят и "несвободный моноид"), поищите. | + | ## '''!!!''' В конспекте упоминается "свободный моноид", но не написано что это такое. Надо написать (в конспекте про моноид), и написать про то, какие еще бывают моноиды (кажется, это называется "моноид с порождающими соотношениями", но, может, говорят и "несвободный моноид"), поищите. |
## Добавить английские аналоги терминам | ## Добавить английские аналоги терминам | ||
| − | # [[Регулярные языки: два определения и их эквивалентность]] | + | # '''!!!''' [[Регулярные языки: два определения и их эквивалентность]] |
## Множества языков (вроде Reg, и Reg') тут зачем-то пишутся курсивом, что вообще не принято, их всегда обозначают большими прямыми (возможно, жирными) буквами. '''Короче, везде надо использовать для классов языков \mathrm!''' | ## Множества языков (вроде Reg, и Reg') тут зачем-то пишутся курсивом, что вообще не принято, их всегда обозначают большими прямыми (возможно, жирными) буквами. '''Короче, везде надо использовать для классов языков \mathrm!''' | ||
## Множества вроде R_i тоже следует обозначать большими прмямыми буквами, так как они перепутываются с языками L, M и т.п.) | ## Множества вроде R_i тоже следует обозначать большими прмямыми буквами, так как они перепутываются с языками L, M и т.п.) | ||
| Строка 25: | Строка 25: | ||
# [[Интерпретация булевых формул с кванторами как игр для двух игроков]] | # [[Интерпретация булевых формул с кванторами как игр для двух игроков]] | ||
#: вообще левая штука, относящаяся скорее к логике. Наверное, надо вообще выпилить это из списка конспектов по автоматам и сделать ссылку из леммы о накачке (оно для нее, видимо, и рассказывалось) | #: вообще левая штука, относящаяся скорее к логике. Наверное, надо вообще выпилить это из списка конспектов по автоматам и сделать ссылку из леммы о накачке (оно для нее, видимо, и рассказывалось) | ||
| − | # [[Доказательство нерегулярности языков: лемма о разрастании]] | + | # '''!!!''' [[Доказательство нерегулярности языков: лемма о разрастании]] |
## пофиксить неправильное доказательство. Точнее, может, оно и правильное, но не нужно, так как не показывает пример нерегулярного языка, для которого лемма о накачке выполняется. | ## пофиксить неправильное доказательство. Точнее, может, оно и правильное, но не нужно, так как не показывает пример нерегулярного языка, для которого лемма о накачке выполняется. | ||
## добавить ссылок на англоязычные источники, добавить в статью англоязычные термины | ## добавить ссылок на англоязычные источники, добавить в статью англоязычные термины | ||
# [[Решение уравнений в регулярных выражениях]] | # [[Решение уравнений в регулярных выражениях]] | ||
| − | # [[Альтернативное доказательство теоремы Клини (через систему уравнений в регулярных выражениях)]] | + | # '''!!!''' [[Альтернативное доказательство теоремы Клини (через систему уравнений в регулярных выражениях)]] |
#: фиг знает что это, но надо написать, видимо | #: фиг знает что это, но надо написать, видимо | ||
# [[Эквивалентность состояний ДКА]] | # [[Эквивалентность состояний ДКА]] | ||
# [[Минимизация ДКА, алгоритм за O(n^2) с построением пар различимых состояний]] | # [[Минимизация ДКА, алгоритм за O(n^2) с построением пар различимых состояний]] | ||
# [[Минимизация ДКА, алгоритм Хопкрофта (сложность O(n log n))]] | # [[Минимизация ДКА, алгоритм Хопкрофта (сложность O(n log n))]] | ||
| − | # [[Контексты и синтаксические моноиды]] | + | # '''!!!''' [[Контексты и синтаксические моноиды]] |
## добавить английских терминов | ## добавить английских терминов | ||
## доказательство последнего утверждения | ## доказательство последнего утверждения | ||
## вообще написать что-нибудь еще бы, типа зачем оно вообще надо. | ## вообще написать что-нибудь еще бы, типа зачем оно вообще надо. | ||
Версия 19:47, 16 октября 2013
Автоматы и регулярные языки
- !!! Основные определения: алфавит, слово, язык, конкатенация, свободный моноид слов; операции над языками
- Добавить сюда определение гомоморфизма, образа и прообраза в соответствующий раздел, взять их отсюда, оттуда соответственно, удалить их определения и сослаться на этот конспект. Еще лучше — создать
- !!! В конспекте упоминается "свободный моноид", но не написано что это такое. Надо написать (в конспекте про моноид), и написать про то, какие еще бывают моноиды (кажется, это называется "моноид с порождающими соотношениями", но, может, говорят и "несвободный моноид"), поищите.
- Добавить английские аналоги терминам
- !!! Регулярные языки: два определения и их эквивалентность
- Множества языков (вроде Reg, и Reg') тут зачем-то пишутся курсивом, что вообще не принято, их всегда обозначают большими прямыми (возможно, жирными) буквами. Короче, везде надо использовать для классов языков \mathrm!
- Множества вроде R_i тоже следует обозначать большими прмямыми буквами, так как они перепутываются с языками L, M и т.п.)
- Мне кажется, первое определение — это по сути означает множество языков, представимое регулярными выражениями, думаю, надо это упомянуть. P.S. Более того, если я не ошибаюсь, кажется, вообще в конспектах нигде нет определения регулярных выражений, так что это определение по сути им является.
- , вот это nadreg выглядит совершенно мерзко, надо от него избавиться. Возможно, найти/придумать разумный английский термин и писать под объединением что-то вроде R is X, где X — это название, которое вы найдется или придумаете.
- Детерминированные конечные автоматы
- Прямое произведение ДКА
- Английские термины
- Добавить ссылку на факт про эквивалентность автоматных и регулярных
- Недетерминированные конечные автоматы
- Английские термины
- Построение по НКА эквивалентного ДКА, алгоритм Томпсона
- Автоматы с eps-переходами. Eps-замыкание
- Теорема Клини (совпадение классов автоматных и регулярных языков)
- Опять классы языков курсивом
- Замкнутость регулярных языков относительно различных операций
- см. 1
- Анализ свойств регулярных языков (пустота, совпадение, включение, конечность, подсчет числа слов)
- выглядит мерзко, такие штуки надо оборачивать в какой-нибудь \mathrm
- Интерпретация булевых формул с кванторами как игр для двух игроков
- вообще левая штука, относящаяся скорее к логике. Наверное, надо вообще выпилить это из списка конспектов по автоматам и сделать ссылку из леммы о накачке (оно для нее, видимо, и рассказывалось)
- !!! Доказательство нерегулярности языков: лемма о разрастании
- пофиксить неправильное доказательство. Точнее, может, оно и правильное, но не нужно, так как не показывает пример нерегулярного языка, для которого лемма о накачке выполняется.
- добавить ссылок на англоязычные источники, добавить в статью англоязычные термины
- Решение уравнений в регулярных выражениях
- !!! Альтернативное доказательство теоремы Клини (через систему уравнений в регулярных выражениях)
- фиг знает что это, но надо написать, видимо
- Эквивалентность состояний ДКА
- Минимизация ДКА, алгоритм за O(n^2) с построением пар различимых состояний
- Минимизация ДКА, алгоритм Хопкрофта (сложность O(n log n))
- !!! Контексты и синтаксические моноиды
- добавить английских терминов
- доказательство последнего утверждения
- вообще написать что-нибудь еще бы, типа зачем оно вообще надо.
