Гистограммная функция автомата и ее приложения

• Автор: Пархоменко, Денис Владимирович
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2015
• Место защиты: Москва
• Количество страниц: 86 с. : ил.

Оглавление
Оглавление
Введение

Глава 1. Гистограммная функция автомата и порождаемые ею языки

1.1 Гистограммная функция автомата и ес свойства

1.2 Классы языков, порожденные гистограммной функцией автомата

1.3 Критерий принадлежности языка к классу ^

1.4 Доказательство критерия принадлежности языка к классу 4». (теоремы 1.5, 1.6 )

Глава 2. Автоматные мультимножества и распознавание с помощью гистограммной автоматной функции
2.1 Алгоритм восстановления гистограммной автоматной функции по конечному мультимножеству

2.2 О классах Ьр - языков

Глава 3. Распознавание через синтез
3.1 Распознавание слов автоматами
3.2 Пример использования гистограммной автоматной функции для распознавания слов
Литература:
Публикации автора по теме диссертации

Введение.
Теория автоматов - раздел дискретной математики, возникший в середине 20-го века в связи с изучением свойств конечных автоматов. Конечный автомат принято определять как устройство, имеющее входной, выходной канал и конечное число состояний. Функционирование автомата осуществляется в дискретной шкале времени: в текущий момент автомат получает на вход один из конечного множества входных сигналов, изменяет текущее состояние и выдает на выход один из конечного множества выходных сигналов. Таким образом, автомат производит отображение входных последовательностей в выходные. Связанное с автоматом отображение называется автоматной функцией.
Сами автоматы и их алгебры начали исследоваться в тридцатые годы предыдущего столетия, но особенно активно в период 50-х годов. С самого возникновения понятия конечного автомата в математике исследовались свойства автоматов порождать языки. Фундаментальный результат в области описания языков, которые можно порождать автоматами опубликовал С.К.Клини [1] в 1956. Клини показал, что представимые в конечных автоматах множества слов в точности совпадают с регулярными языками.

Предпосылкой к формированию теории автоматов явилась фундаментальная статья Мак-Каллока и Питтса [14] о логическом анализе нервной деятельности. Однако, исторически первой работой, давшей толчок к развитию теории автоматов, является работа Э. Поста 1941 года [2]. В ней была описана структура решетки замкнутых классов булевых функций. Нулевые функции являются частным случаем автоматов - автоматами без памяти. Возникшие для булевых функций, а также для функции /с-значной логики [15], задачи о выразимости, полноте, базисах актуальны и для автоматных функций. Применим к ним и аппарат, используемый для решения этих задач. Под выразимостью здесь понимается возможность получения одной автоматной функций через другие автоматные функции. Частным случаем задачи выразимости является задача полноты, в которой проверяется возможность выразимости всех автоматных функций. Этот подход носит название структурной теории автоматов. Значительный вклад в развитие структурной теории автоматов внесли В.Б.Кудрявцев [4], А.А.Летичевский [12], М.И.Кратко [13], С.В. Алёшин [16], Д.Н.Бабин [3], В.А. Буевич.
В настоящей работе автор предлагает новый тип поведения автоматов, когда множество распознаваемых автоматом слов порождается частотными свойствами автоматной функции.
Под конечным детерминированным инициальным автоматом V, согласно [4], будем понимать шестерку
V=(A,Q,B,
Рисунок 9. Автомат V с раскрашенными состояниями.
Пусть V задает регулярный язык Ь с помощью состояния д2 множества состояний. Ь= {1(0*(11)*)*}. Покажем, что Ье для чего предъявим источник Ж: Ь=Ь2(Т¥).
Используя диаграмму переходов автомата V, построим источник Ж: пусть каждому состоянию де {до,41,42} соответствует набор 0(4)={ч1ч ,... ,змд} состояний источника IV, причем М=к(д). Таким образом, в новом источнике будет 1 состояние, «порожденное» 4о, и 2 состояния, «порожденные» д2, выделенные на рисунке 9 слева соответствующим цветом. Так как теперь буква 1еЕ2 такова, что <р(до,1)=42, то соединим наборы состояний 0(4о)={$о} и 0(д2) ^{^ 2, ^2}, проведя к(д2) =2 нагруженных символом 1 ребра из Бо в у7,, у22. Аналогично для д2 и символа 0 и /. Полученный источник IVудовлетворяет: Ь2(ТУ)={ 1(0*(11)*)*}=Ь.
Покажем теперь, что если язык для источника (Г, и автомат
У=(Е3,{д0,д 1,42,43,44}, <Р, 4о, Яр) над Е3={0,1,2} представляет!, с помощью множества финальных состояний <2р={4з}, то найдется автомат V’, представляющего язык Ь с помощью финальных состояний, который можно правильно /»-раскрасить. Диаграмма автомата V представлена на рисунке: