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