Категория
Информатика
Тип
реферат
Страницы
12 стр.
Дата
25.01.2009
Формат файла
.rtf — Rich Text Format (Wordpad)
Архив
21114.zip — 9.38 kb
  • determinirovannye-i-nedeterminirovannye-konechnye-avtomaty_21114_1.rtf — 54.2 Kb
  • Readme_docus.me.txt — 125 Bytes
Рейтинг
10  из 10
Оценок
1
Оцените работу
Хорошо  или  Плохо


Текст работы

Slay Slay
1. Введение
В настоящем реферате будут даны определения детермини рованных и недетерминированных конечных автоматов, приведе ны их графы. Далее будет рассмотрен случай преобразования
недетерминированного конечного автомата в детерминированный
с рисунками и графами.
Все рассмотренные здесь автоматы представлены как маши ны, распознающие цепочки символов.
2. Детерминированные конечные автоматы.
В различных источниках приводятся несколько отличающие ся друг от друга определения детерминированного конечного
автомата. Приведем здесь определение из источника [2].
Детерминированным конечным автоматом (ДКА) называется
машина, распознающая цепочки символов. Она имеет входную
ленту, разбитую на клетки, головку на входной ленте (вход ную головку) и управляющее устройство с конечным числом
состояний (рис. 1). Конечный автомат М можно представить в
виде пятерки (S, I, 1б 0, 1s0 0, F), где
1) S - множество состояний 1управляющего устройства 0,
2) I - 1входной алфавит 0(каждая клетка входной ленты со держит символ из I),
3) 1б 0 - отображение из S x I в S (если 1б 0( 1s 0, 1a 0) = 1s' 0, то
всякий раз, когда М находится в состоянии 1s 0, а входная
головка обозревает символ 1a 0, М сдвигает входную головку
вправо и переходит в состояние 1 s' 0),
4) 1 s0 0 - выделенное состояние в S, называемое 1начальным 0,
5) F - подмножество в S, называемое множеством 1допуска 1ющих 0 (или 1 заключительных 0) 1 состояний 0.
│'a6 1b 0 │'a6 1a 0 │'a6 1c 0 │'a6 Входная лента
^
│'a6 Головка
┌'2d─'2d─'2d┴'2b─'2d─'2d┐'ac
│'a6 1s 0 │'a6 Управляющее устройство
└'4c─'2d─'2d─'2d─'2d─'2d┘'2d
Рис. 1. Конечный



Ваше мнение



CAPTCHA