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.

┌─────┬─────┬─────┐

│  1b 0 │  1a 0 │  1c 0 │ Входная лента

└─────┴─────┴─────┘

^

│ Головка

┌──┴──┐

│  1s 0 │ Управляющее устройство

└─────┘

Рис. 1. Конечный автомат

ДКА выполняет шаги, определяемые текущим состоянием его


блока управления и входным символом, обозреваемым входной

головкой. Каждый шаг состоит из перехода в новое состояние

и сдвига входной головки на одну клетку вправо. Оказывает-

ся, что язык представим регулярным [2] выражением тогда и

только тогда, когда он допускается некоторым конечным авто-

матом.

Далее будет приведено определение ДКА через определение

недетерминированного конечного автомата (НКА), то-есть

можно будет рассматривать ДКА в качестве подмножества НДКА.

2. Недетерминированные конечные автоматы

Для каждого состояния и каждого входного символа НКА

имеет нуль или более вариантов выбора следующего шага. Он

может также выбирать, сдвигать ему входную головку при из-

менении состояния или нет.

Приведем определение недетерминированного конечного ав-

томата.

Недетерминированным конечным автоматом называется пя-

терка (S, I, 1 б 0, 1 s0 0, F), где

1) S - конечное множество состояний устройства управле-

ния;

2) I - 1 алфавит 0 входных символов;

3)  1б  0-  1функция переходов 0, отображающая S x (I U { 1e 0}) в

множество подмножеств множества S;

4) 1 s0 0 (- S - 1 начальное состояние 0 устройства управления;

 5) F  _(  .S - множество  1заключительных (допускающих)  0сос-

тояний.

С каждым НКА связан ориентированный граф, естественным

образом представляющий функцию переходов этого автомата.

Приведем определение для графа ( или диаграммы) перехо-

дов автомата М = (S, I,  1б 0,  1s0 0, F).

Графом переходов автомата М называют ориентированный

граф G = (S, E) с помеченными ребрами. Множество ребер Е и

метки определяются следующим образом. Если  1б(s, a)  0содержит

 1s'  0для некоторого  1a  0(- I U { 1e 0}, то ребро  1(s, s')  0принадле-

жит Е. Меткой ребра  1(s, s')  0служит множество тех  1b  0(- I U

{ 1e 0}, для которых 1 б(s, b) 0 содержит 1 s' 0.

Например на рис. 2. изображен граф переходов для неко-

торого НКА. Заключительное состояние обведено двойной рам-

кой.


┌─────┐

 1a,b 0 │ v

│ ┌─────┐  1a 0 ┌─────┐

└──┤  1s1 0 ├────────────────────_│  1s2 0 │

└─────┘ ┌──────────_└──┬──┘

^ │ │

│  1e 0 │ │

└────────────┼───────┐ │  1b

│ │ │

 1e 0 │ │ │

│ │ v

┌=====┐─────────┘ └── ┌─────┐

│  1s4 0 │_────────────────────┤  1s3 0 │

└=====┘  1 a 0 └─────┘

Рис. 2. Пример графа переходов

Для дальнейшего рассмотрения вопроса приведения недер-

минированного конечного автомата к детерминированному, пот-

ребуется указать несколько теорем. Теоремы приведены без

доказательства, для их подробного рассмотрения предлагается

обратиться к [2].

 _Теорема 1.  .Всякий язык, допускаемый недерминированным

конечным автоматом регулярен.

 _Теорема 2.  .Пусть  2а 0 - регулярное выражение. Тогда най-

дется НКА М = (S, I,  1б 0,  1s0 0, { 1Sf 0}), допускающий язык, предс-

тавленный  2а 0, и обладающий такими свойствами:

1) ││S││ < = 2│ 2a 0│, где │ 2а 0│ - длина выражения 2 а 0,

2) для каждого  1a 0 (- I U { 1e 0} множество 1 б(Sf, a) 0 пусто,

3) для каждого  1s  0(- S сумма чисел ││ 1б(s, a) 0││ по всем  1а

из I U { 1e 0} не превосходит 2.

Эти теоремы будут использованы при преобразовании НКА в

ДКА в следующем пункте.


Информация о работе «Конечные автоматы»
Раздел: Информатика, программирование
Количество знаков с пробелами: 17214
Количество таблиц: 0
Количество изображений: 0

Похожие работы

Скачать
14593
2
12

... цифр с требуемым числом разрядов и, таким образом, запомнить любое самое большое число данной разрядности. Целью данной курсовой работы является ЛИСП-реализация конечных автоматов.1. Постановка задачи Конечный автомат – автомат, проверяющий допустимость слова на ленте, и возвращающий True / False (в данном случае Correct / Incorrect). Конечный автомат может двигаться по ленте только в одном ...

Скачать
42602
16
0

... базису, состоящему всего из одной функции. Были построены комбинационные схемы, иллюстрирующие полученные результаты. Выгода рассмотренных преобразований функций становится очевидной при их практической реализации на стандартизованных электронных микросхемах. 2 Синтез конечных автоматов 2.1 Постановка задачи Конечный автомат задан своими уравнениями переходов и ...

Скачать
16157
12
0

... требует построения устройства памяти для запоминания текущего состояния автомата. Обычно используются двоичные элементы памяти, или триггеры, запоминающие значение одного двоичного разряда. 1. АБСТРАКТНЫЙ СИНТЕЗ КОНЕЧНОГО АВТОМАТА   1.1 Формирование алфавитного оператора   Для определения параметров задания необходимо ввести первичную информацию: - порядковый номер в журнале; - год ...

Скачать
25189
5
5

... . Такое предположение перестает быть реалистичным, если при тестировании нет возможности полностью контролировать проверяемый автомат, что имеет место, например, при удаленном тестировании реализаций телекоммуникационных протоколов. В данной работе изучен метод построения полного проверяющего теста относительно модели неисправности <S, (£,≁),Âm >, предложенный в работе [1]. ...

0 комментариев


Наверх