|
ИСТИНА |
Войти в систему Регистрация |
ФНКЦ РР |
||
Некоторые классы функций, вычислимые автоматамидипломная работа (Специалист)
- Научный руководитель: Бабин Д.Н.
- Автор: Иванов Илья Евгеньевич
- Тип: Специалист
- Организация, в которой проходила защита: МГУ имени М.В. Ломоносова, механико-математический факультет
- Год защиты: 2011
- Аннотация: Согласно классификации формальных языков Хомского каждому типу языка сопоставлен акцептор — вычислительное устройство, распознающее данный язык. Для регулярных языков акцептором является конечный автомат, для контестно-свободных — автомат с магазинной памятью, для контестно-зависимых — линейно-ограниченная машина Тьюринга, для языков, порожденных грамматиками общего вида, — машина Тьюринга. Аналогично, можно классифицировать и функции f : Z+ → Z+ по типу вычисляющего устройства. Хорошо известен класс вычислимых функций, то есть функций, вычисляемых машиной Тьюринга. В работе исследуются классы функций, вычисляемых конечными автоматами, автоматами с магазинной памятью,автоматами с 2 магазинами.
- Добавил в систему: Бабин Дмитрий Николаевич