Регулярное выражение несет регулярный язык; для всякого регулярного языка имеется несущее его регулярное в
Работа добавлена на сайт samzan.net: 2016-03-30
Поможем написать учебную работу
Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
от 25%
Подписываем
договор
- Лемма. Регулярное выражение несет регулярный язык; для всякого регулярного языка имеется несущее его регулярное выражение.
ZM, стр.5, но ни хера не доказано.
- Теорема. Эквивалентность конечных автоматов над Σ разрешима.
ZM стр. 17
- Алгоритм Мура. Описание и доказательство корректности.
ZM стр. 17 — описание; доказательство корректности есть в её методичке
- Теорема. Существует алгоритм, который для всякого недетерминированного конечного автомата строит эквивалентный ему детерминированный.
Хз, где искать.
- Теорема Клини (часть 1). Существует алгоритм, который по всякому графу переходов T строит регулярное выражение R такое, что = .
ZM стр. 11
- Теорема Клини (часть 2). Существует алгоритм, который по всякому регулярному выражению R строит конечный автомат A такой, что = .
ZM стр. 14
- Теорема Поста (часть 1). По машине Тьюринга над Σ можно построить адекватную ей машину Поста над Σ.
ZM стр. 27
- Теорема Поста (часть 2). По машине Поста над Σ можно построить эквивалентную ей машину Тьюринга над Σ.
ZM стр. 28
- Теорема Минского (часть1). По машине Тьюринга над Σ можно построить адекватную ей машину с двумя магазинами над Σ.
ZM стр. 33
- Теорема Минского (часть2). По машине с двумя магазинами над Σ можно построить эквивалентную ей машину Тьюринга над Σ.
ZM стр. 34
- Классификация по мощности детерминированных и недетерминированных конечных машин над Σ без магазинов, с одним, двумя и более магазинами.
ZM стр. 37
- Соотношения между рекурсивными и рекурсивно перечислимыми множествами.
ZM стр. 40
- Иерархия формальных языков над Σ типа 0, 1, 2, 3.
ZM стр. 43
- Теорема Тьюринга. Проблема остановки машин Тьюринга над Σ неразрешима.
ZM стр. 56
- Неразрешимость проблемы остановки машин Тьюринга на пустой ленте, униформной проблемы остановки машин Тьюринга.
ZM стр. 57
- Неразрешимость тотальности частично рекурсивных функций.
Это упоминается где-то там, но доказательства я не нашла.
- Теорема Поста о неразрешимости проблемы слова для систем полу-Туэ.
ZM стр. 59
- Теорема Поста о неразрешимости проблемы соответствия Поста.
ZM стр. 61
- Соотношение между разрешимостью и частичной разрешимостью проблем.
ZM стр. 65
- Частичная неразрешимость проблемы неостановки машин Тьюринга.
ZM стр. 65 — но где доказательство?
- Неразрешимые проблемы для формальных языков.
ZM стр. 63