Конечные автоматы Введение



страница1/18
Дата21.12.2012
Размер1.17 Mb.
ТипДокументы
  1   2   3   4   5   6   7   8   9   ...   18

Конечные автоматы




  • Введение



В основе теории построения компиляторов лежит теория автоматов. Под автоматом подразумевается некоторая математическая модель, свойства и поведение которой можно изучать и которую можно имитировать с помощью программы на реальной вычислительной машине. Конечный автомат является простейшей из моделей теории автоматов и служит управляющим устройством для всех остальных, изучаемых в ней автоматов.

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

  1. Конечный автомат может решать (по крайней мере, в первом приближении) ряд легких задач компиляции. В частности, лексический блок почти всегда строится на основе конечного автомата.

  2. Поскольку при моделировании конечного автомата на вычислительной машине обработка одного входного символа требует небольшого количества операций, программа работает быстро.

  3. Моделирование конечного автомата требует фиксированного объема памяти, что упрощает проблемы, связанные с управлением памятью.

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


Термин «конечный автомат» в действительности употребляется в разных смыслах — в зависимости от подразумеваемых приложений. В литературе по теории автоматов существует несколько различных формальных определений. Общим в этих определениях является то, что они моделируют вычислительные устройства с фиксированным и конечным объемом памяти, которые читают последовательности входных символов, принадлежащих некоторому конечному множеству. Принципиальные различия в определениях связаны с тем, что автоматы делают на выходе. Следующий раздел начинается с рассмотрения конечного автомата, единственным «выходом» которого является указание на то, «допустима» или нет данная входная цепочка (последовательность символов). «Допустимой» мы называем «правильно построенную» или «синтаксически правильную» цепочку; например, цепочка, которая должна изображать числовую константу, построена не правильно, если содержит две десятичные точки.
    1. Конечные распознаватели



Конечный распознаватель — это модель устройства с конечным числом состояний, которое отличает правильно образованные или «допустимые» цепочки от недопустимых. Хотя это понятие чисто математическое, определяемое в терминах множеств, последовательностей (цепочек) и функций, лучше представлять его себе в виде вычислительной машины.

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

На вход конечного автомата подается цепочка символов из конечного множества, называемого входным алфавитом автомата и представляющего собой совокупность символов, для работы с которыми он предназначен. Как допускаемые, так и отвергаемые автоматом цепочки состоят только из символов входного алфавита. Символы, не принадлежащие входному алфавиту, нельзя подавать на вход автомата. Входной алфавит контролера нечетности состоит из двух символов: 0 и 1.

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

Контролер нечетности будет построен так, чтобы он умел запоминать, четное или нечетное число единиц встретилось ему при чтении отрезка входной цепочки. Поэтому множество состояний нашего автомата содержит два состояния, которые мы будем называть ЧЕТ и НЕЧЕТ.

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

При чтении очередного входного символа состояние автомата меняется, причем новое его состояние зависит только от входного символа и текущего состояния. Такое изменение состояния называется переходом. Может оказаться, что новое состояние совпадает со старым.

Работу автомата можно описать математически с помощью функции δ, называемой функцией переходов. По текущему состоянию Sтек и текущему входному символу х она дает новое состояние автомата Sнов. Символически эта зависимость описывается так:

δ (Sтек, х) = Sнов

Учитывая, что состояния ЧЕТ и НЕЧЕТ означают соответственно четное и нечетное число прочитанных единиц, определим функцию переходов контролера нечетности следующим образом:

δ (ЧЕТ, 0) = ЧЕТ

δ (ЧЕТ, 1) = НЕЧЕТ

δ (НЕЧЕТ, 0) = НЕЧЕТ

δ (НЕЧЕТ, 1) = ЧЕТ

Эта функция переходов отражает тот факт, что четность меняется тогда и только тогда, когда на входе читается единица.

Некоторые состояния автомата выбираются в качестве допускающих или заключительных. Если автомат, начав работу в начальном состоянии, при прочтении всей цепочки переходит в одно из допускающих состояний, говорят, что эта входная цепочка допускается автоматом. Если последнее состояние автомата не является допускающим, говорят, что автомат отвергает цепочку. Контролер нечетности имеет единственное допускающее состояние — НЕЧЕТ.

Суммируя все сказанное, можно дать следующее определение конечного распознавателя.

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

  1. конечным множеством входных символов,

  2. конечным множеством состояний,

  3. функцией переходов δ, которая каждой паре, состоящей из входного символа и текущего состояния, приписывает некоторое новое состояние,

  4. состоянием, выделенным в качестве начального, и

  5. подмножеством состояний, выделенных в качестве допускающих или заключительных.


Переход автомата из состояния Sтек в состояние Sнов при чтении входного символа х будем наглядно изображать так:

Sтек х Sнов


Для контролера нечетности, например, можно написать

НЕЧЕТ 1 ЧЕТ

Аналогичным образом можно изобразить последовательность переходов. Например, запись

ЧЕТ 1 НЕЧЕТ 1 ЧЕТ 0 ЧЕТ 1 НЕЧЕТ

показывает, как автомат в состоянии ЧЕТ применяется к цепочке 1101. Первый символ 1 меняет состояние ЧЕТ на НЕЧЕТ, так как δ (ЧЕТ, 1) = НЕЧЕТ. Следующая единица меняет НЕЧЕТ на ЧЕТ. Нуль оставляет автомат в состоянии ЧЕТ. Последняя единица изменяет состояние на НЕЧЕТ. Так как ЧЕТ — начальное, а НЕЧЕТ— допускающее состояние, цепочка 1101 допускается нашим автоматом.

Входную цепочку 101 автомат отвергает, так как она переводит его из начального состояния в состояние, не являющееся допускающим. Символически это изображается так:

ЧЕТ 1 НЕЧЕТ 0 НЕЧЕТ 1 ЧЕТ


Иногда мы хотим говорить о множестве всех цепочек, распознаваемых некоторым конечным автоматом. Например, контролер нечетности распознает множество цепочек, состоящих из нулей и единиц и содержащих нечетное число единиц. Такие множества обычно называют «регулярными».

Регулярным множеством называется множество цепочек, которое распознается некоторым конечным распознавателем.

Таким образом, множество цепочек из нулей и единиц с нечетным числом единиц может служить примером регулярного множества.
  1   2   3   4   5   6   7   8   9   ...   18

Похожие:

Конечные автоматы Введение iconИсследование по преобразованию регулярного выражения в конечные автоматы. И, соответственно, заключение, выводы по теме
Далее уже рассказываем теоретические материалы про детерминированные и недетерминированные конечные автоматы, разбираем одну небольшую...
Конечные автоматы Введение iconИсторический очерк развития криптографии. Конечные автоматы, регулярность, наследственность, бпи-автоматы
Классы сложности. Труднорешаемость. Применение труднорешаемых задач для построения шифров. Примеры
Конечные автоматы Введение iconО настройке поведения взаимодействующих процессов
Ключевые слова: конечные автоматы, комбинаторные автоматы, полугруппы, комбинаторные моноиды
Конечные автоматы Введение iconРаспределенные конечные автоматы

Конечные автоматы Введение iconКонечные автоматы
Однако существуют способы решения подобных задач, существенно облегчающие написание программы. Одним из таких способов является построение...
Конечные автоматы Введение iconТеория автоматов Конечные автоматы. Конечный автомат
Автомат называется частичным, если некоторым парам из множества QxA не сопоставлены элементы из множества QxB
Конечные автоматы Введение iconКонечные автоматы
Здесь рассматривается реализация конечного автомата на языке JavaScript на примере решения простой задачи смены картинок. Данный...
Конечные автоматы Введение iconИнтервью по сбору фактов. Упражнения по построению функциональной модели в ходе интервью
Зачем нужно моделирование. Модель как проекция. Цель, границы и точка зрения модели. Различные подходы к моделированию (конечные...
Конечные автоматы Введение iconНеизбыточные алгоритмы обхода ориентированных графов. Недетерминированнный случай
Данная статья является продолжением статьи [18], которая была посвящена обходу детерминированных графов как основе тестирования конечных...
Конечные автоматы Введение iconФормальные грамматики: классификация. Абстрактные автоматы: определение, поведение
Абстрактные автоматы: способы представления, автомат с линейно ограниченной памятью
Разместите кнопку на своём сайте:
ru.convdocs.org


База данных защищена авторским правом ©ru.convdocs.org 2016
обратиться к администрации
ru.convdocs.org