Конечные автоматы (46030)

Посмотреть архив целиком


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.


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

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



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


Существует дополнительный результат или возможность со-

поставить какому-либо взятому НКА эквивалентную "детермини-

рованную" машину. Однако детерминированный конечный авто-

мат, эквивалентный данному НКА с n состояниями, может иметь

вплоть до 2 в n степени состояний. Поэтому переход от НКА к

детерминированному автомату не всегда дает эффективный спо-

соб моделирования недетерминированного конечного автомата.



Однако ДКА позволяют проще формализовать модель автомата и

алгоритмизировать его поведение. Кроме этого детерминиро-

ванные автоматы применяются при распознавании образов.

Таким образом мы можем дать определение ДКА как подмно-

жества или частного случая НКА.

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

терминированный конечный автомат (S, I,  1б 0,  1s0 0, F), в кото-

ром:

1) 1 б(s, e) 0 = (/) (пустое множество) для всех 1 s 0 (- S,

2) ││ 1б(s, a) 0││ < = 1 для всех 1 s 0 (- S и 1 а 0 (- I.


Приведем теорему, которая поможет связать и выразить

недетерминированный конечный автомат через его детерминиро-

ванный эквивалент.


 _Теорема 3.  .Если L - регулярное множество, то оно допус-

кается некоторым ДКА.


Доказательство. По теореме 1 L допускается некоторым


Случайные файлы

Файл
158747.rtf
114419.rtf
30311.rtf
57612.rtf
8059-1.rtf




Чтобы не видеть здесь видео-рекламу достаточно стать зарегистрированным пользователем.
Чтобы не видеть никакую рекламу на сайте, нужно стать VIP-пользователем.
Это можно сделать совершенно бесплатно. Читайте подробности тут.