ОПРЕДЕЛЕНИЕ И СВОЙСТВА КОНЕЧНЫХ АВТОМАТОВ

Курсовая работа

 

Чита 2019

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

Федеральное государственное бюджетное образовательное учреждение высшего образования

«Забайкальский государственный университет»

(ФГБОУ ВПО «ЗабГУ»)

 

Энергетический факультет

 

Кафедра информатики, вычислительной техники и прикладной математики

 

ПОЯСНИТЕЛЬНАЯ ЗАПИСКА

к курсовому проекту

 

по специальности 09.03.01 «Информатика и вычислительная техника»

 

 

На тему «Программа преобразования НКА в ДКА»

 

 

Выполнил студент группы ИВТ-16-1 Мархандаев Сергей Викторович

 

 

Руководитель работы

Доцент кафедры ИВТиПМ Соловьев Владимир Александрович             

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

Федеральное государственное бюджетное образовательное учреждение высшего образования

«Забайкальский государственный университет»

(ФГБОУ ВПО «ЗабГУ»)

 

Энергетический факультет

 

Кафедра информатики, вычислительной техники и прикладной математики

 

 

ЗАДАНИЕ

на курсовой проект

 

по курсу «Теория автоматов»

 

Студенту Мархандаеву Сергею Викторовичу

 

Тема работы «Программа преобразования НКА в ДКА» утверждена приказом по университету от «___» _______________ 20___ г. № _____

 

Исходные данные к работе:

Нормативно-техническая документация

Источники в сети Интернет

 

Рекомендуемая литература:

 

а) Хопкрофт, Джон Э., Мотвани, Раджив, Ульман, Джеффри Д. Введение в теорию автоматов, языков и вычислений, 2-е издание – : Перевод с английского – М.: Вильямс, 2008 – 528 с.

 

б) Горбунов, А. Н. Модели динамической логики. Учебное пособие — Брянск: БГТУ, 2001. — 109 с.

 

Графическая часть на 0 листах

Дата выдачи задания «9» сентября 2019 г.

Руководитель Доцент кафедры ИВТиПМ Соловьев Владимир Александрович

Дата представления студентом законченной работы «30» декабря 2019 г.

 

Задание принял к исполнению «9» сентября 2019 г.

Подпись студента __________________

РЕФЕРАТ

Пояснительная записка –  14 с.

 

ТЕОРИЯ АВТОМАТОВ, КОНЕЧНЫЙ АВТОМАТ, АЛФАВИТ, ЯЗЫК, СИМВОЛ, ЦЕПОЧКА, ДЕТЕРМИНИРОВАННЫЙ КОНЕЧНЫЙ АВТОМАТ, НЕДЕТЕРМИНИРОВАННЫЙ КОНЕЧНЫЙ АВТОМАТ, ДОПУСКАЮЩЕЕ СОСТОЯНИЕ, МНОЖЕСТВО СОСТОЯНИЙ, ЭКВИВАЛЕНТНОСТЬ АВТОМАТОВ, АЛГОРИТМ ПРЕОБРАЗОВАНИЯ ДКА В НКА

 

Теория автоматов как раздел теории алгоритмов. Структурная теория автоматов. Конечные автоматы, из чего они состоят. Формальное определение конечного автомата. Как конечный автомат допускает цепочки символов. Различие между недетерминированным и детерминированным конечным автоматом. Эквивалентность конечных автоматов. Создание ДКА, эквивалентного НКА. Алгоритм Томпсона.

СОДЕРЖАНИЕ

ВВЕДЕНИЕ................................................................................................................................... 6

1. ОПРЕДЕЛЕНИЕ И СВОЙСТВА КОНЕЧНЫХ АВТОМАТОВ......................................... 8

1.1. Определение....................................................................................................................... 8

1.2. Недетерминированный конечный автомат.................................................................. 10

1.2. Преобразование НКА в ДКА......................................................................................... 11

2. АЛГОРИТМ ПРЕОБРАЗОВАНИЯ НКА В ДКА............................................................... 12

ЗАКЛЮЧЕНИЕ........................................................................................................................... 13

СПИСОК ИСПОЛЬЗУЕМЫХ ИСТОЧНИКОВ...................................................................... 14

 

ВВЕДЕНИЕ

Автомат – это абстрактная модель дискретного устройства, разновидность алгоритма, предназначенного для распознавания и преобразования символов.

Автоматы используются при создании синтаксических анализаторов, для ограничения пользовательского ввода, анализа протоколов.

Активное развитие теории автоматов пришлось на период с начала 60-х по конец 90-х гг. XX века [1]. Сегодня она имеет больше прикладное значение, в ней имеется лишь узкое направление для исследований. Несмотря на это, теория автоматов, наряду с теорией сложности, являются очень важной частью ядра информатики [2].

Все многообразие видов цифровых машин можно отнести к одному классу конечных автоматов. Это означает, что они обладают следующими общими свойствами. Во-первых, всякая цифровая вычислительная машина состоит из конечного множества элементов, каждый из которых в любой данный момент времени может находиться лишь в одном из конечного числа устойчивых состояний. Поэтому и вся машина имеет лишь конечное множество устойчивых состояний. Во-вторых, каждая цифровая машина работает последовательно: ее операции синхронизированы сигналами тщательно настроенных электронных часов (обычно от 106 до 109 сигналов в секунду). В соответствии с этим состояния машины меняются в четкой последовательности. В-третьих, цифровая вычислительная машина является детерминированным устройством: при наличии полной информации о внутренних состояниях всех элементов машины и всех ее входов следующее состояние машины определено однозначно.

Почти все цифровые машины конструируются на электронных схемах и других элементах, имеющих два устойчивых состояния. Основные причины этого – технологические. Быстродействие электронных схем увеличивается, если в качестве рабочих взяты два крайних состояния; надежность также возрастает, ибо в этом случае небольшие отклонения характеристик не отражаются на устойчивости схемы. Итак, схемы и сигналы по большей части двузначны. Любой конкретный электрический сигнал, если исключить переходный период, принимает одно из двух значений.[3]

 

Цель настоящей работы состоит в исследовании программного пути преобразования НКА в ДКА.

Для достижения поставленной цели необходимо решить следующие задачи:

– Найти информацию, касающуюся НКА и ДКА в теории автоматов;

– Усвоить и осознать ее;

– Написать программу для преобразования НКА в ДКА.

Объектом данной работы – раздел теории автоматов, касающийся конечных автоматов.

Предмет работы – преобразование недетерминированного конечного автомата в детерминированный.

Теоретическую основу работы составляют научные труды отечественных и зарубежных ученых по вопросам теории автоматов. Основным методом исследования в работе выступил системный метод. Эмпирическую базу работы составили статистические и отчётные данные, данные публикуемые в сети Интернет.

Практическая значимость работы заключается в приобретении навыков программирования, освоение принципов подготовки и оформления документации, изучение возможностей текстового процессора и основ подготовки презентаций.

ОПРЕДЕЛЕНИЕ И СВОЙСТВА КОНЕЧНЫХ АВТОМАТОВ

Определение

Конечный автомат – состоящий из конечного числа состояний автомат, допускающий либо не допускающий определенную определенную цепочку символов.

 

Конечный автомат состоит из:

1. Конечное множество состояний Q.

2. Конечное множество входных символов Σ (алфавит).

3. Функция переходов δ.

4. Начальное состояние q.

5. Множество допускающих состояний F.

Автомат в один момент времени может находиться в определенном состоянии из множества Q. Они обычно обозначаются как q ₁, q ₂, ...

Автомат способен воспринимать символы, если они принадлежат Σ. В каждом состоянии он воспринимает один символ, а затем переключается на следующий.

Автомат может переходить из одного состояние в другое. Эти переходы совершаются при помощи функции переходов δ. Она в зависимости от того, в каком состоянии находится автомат, и какой символ он воспринял, находясь в этом состоянии, определяет следующее состояние, в котором окажется автомат.

В начале работы автомат находится в начальном состоянии q.

Если в процессе переходов из одного состояния в другое какое-либо из состояний окажется допускающим, то автомат допускает последовательность входных символов. При этом должны быть прочитаны все символы входной цепочки.

Автомат при начале работы получает входную цепочку, состоящую из символов алфавита. Начальному состоянию автомата соответствует первый символ цепочки. Затем автомат движется по цепочке слева направо, принимая те или иные состояния в зависимости от воспринимаемых им символов. Если после прочтения всех символов автомат перешел в одно из допускающих состояний (на самом деле, их необязательно должно быть больше одного), то эта цепочка считается допущенной.

Множество всех допускаемых этим автоматом цепочек называется языком.[2]

Свойства автоматов [4]:

1. наличие начального и конечного состояний;

2. дискретность;

3. массовость (обрабатываемые данные должны лежать в некотором

4. диапазоне);

5. определенность (четкий переход от состояния к состоянию при за-

6. данной последовательности входных сигналов);

7. понятность (исполнителю);

8. результативность (конечность);

9. корректность (получение правильного результата).