8926

Лекции по теории автоматов Часть 1 Теория абстрактных автоматов

Конспект

Коммуникация, связь, радиоэлектроника и цифровые приборы

Лекции по теории автоматов Часть 1 Теория абстрактных автоматов Учебное пособие для студентов очной и заочной форм обучения специальностям в области вычислительной техники, информатики и управления. ОГЛАВЛЕНИЕ Часть 1. Теория абстрактных автоматов...

Русский

2013-02-21

241 KB

156 чел.

Лекции по теории автоматов

Часть 1

Теория абстрактных автоматов

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


ОГЛАВЛЕНИЕ

Часть 1. Теория абстрактных автоматов…………………………………………………..3

  1.1. Общие сведения……………………………..………………………………………..3

  1.2. Способы задания автоматов…………………………………………………………4

  1.3. Примеры абстрактных автоматов, выполняющих полезные действия…………...6

  1.4. Поведение изолированного синхронного автомата………………………………..8

  1.5. Регулярные выражения и конечные автоматы…………………………………….10

  1.6. Алгоритмы и машины Тьюринга….………………………………………………...11

  1.7. Элементы теории формальных грамматик и языков………………………………15

  1.8. Условия автоматности отображения………………………………………………..20

  1.9. Построение графа автомата по входо-выходным последовательностям…………21

 1.10. Преобразование автоматов………………………………………………………….22

  Задачи и упражнения.……………………………………………………………………..24

  Литература…………………………………………………………………………………25


ЧАСТЬ 1. ТЕОРИЯ АБСТРАКТНЫХ АВТОМАТОВ

1.1. Общие сведения

Абстрактный автомат (АА) – дискретный преобразователь информации; представляет собой множество, состоящее из шести элементов:

S = {X, Q, Y, δ, λ, q1}

S – абстрактный автомат;

X – множество входных символов (входной алфавит автомата):

X = {x1, ... , xm};

Q множество состояний автомата:

Q = {q1, ... , qn};

Y – множество выходных символов (выходной алфавит автомата):

Y = {y1, ... , yp};

δ – функция переходов автомата из одного состояния в другое:

qj = δ(qi, xk),

где: qj – следующее (новое) состояние автомата; qi – текущее состояние автомата;
               
xk – текущий входной символ;

λ – функция выходов:

yl = λ (qi, xk);

q1 – начальное состояние автомата (применяется также обозначение q0).

Автомат называется конечным, если множества  X, Q, Y – конечны.

       

Рис.1. Представление абстрактного автомата

На рис. 1  t – дискретное время: t = nT, где T – интервал (такт), разделяющий дискретные моменты времени; если  T = 1,  то  t = n,  т. е. дискретное время сопоставляется упорядоченному ряду натуральных чисел.

Абстрактный автомат (АА) можно рассматривать как "черный ящик" с одним входом и одним выходом, с которым можно экспериментировать, не зная, что находится внутри.

Выходной символ (yl  Y) зависит не только от входного символа (x  X), но и от
того, в каком состоянии (
qi  Q) находится автомат. Автомат функционирует в дискретном времени; это означает, что элементы описания автомата заданы только в упомянутые выше дискретные моменты.

Представим, что с некоторого начального, например, нулевого момента времени на вход автомата подаются входные символы, образующие входное слово некоторой длины (длина любого i-го слова измеряется числом символов). На выходе получаем выходное слово той же длины (рис. 2).

Рис.2. Преобразование входных слов в выходные

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

На практике широкое распространение получили две основные модели, описывающие функционирование АА:

1. Модель Мили;

2. Модель Мура.

Модель Мили.

Законы функционирования автомата Мили представлены следующим образом:

q(t+1) = δ(q(t), x(t))

y(t) = λ(q(t), x(t))

t – текущий момент времени;

t+1 – следующий момент времени;

q(t+1) – состояние автомата в следующий момент времени;

q(t), x(t), y(t) – элементы описания автомата в текущий момент времени.

Модель Мура.

Законы функционирования автомата Мура представлены следующим образом:

q(t+1) = δ(q(t), x(t))

y(t) = λ(q(t))

В модели Мура выходной сигнал явно зависит только от состояния, а косвенно –
и от входного сигнала.

Любой автомат можно спроектировать по той или иной модели.

1.2. Способы задания автоматов

Рассмотри два основных способов задания автоматов:

1. Табличный способ

Автомат Мили

Для автомата Мили табличный способ заключается в построении двух таблиц: таблицы переходов (ТП) и таблицы выходов (ТВ).

x\q

qi

x\q

qi

.

.

.

.

.

.

xk

(qi,xk)

xk

(qi,xk)

 .

.

.

.

.

.

                                       а                                                    б

Рис. 3.  Табличный способ: а – таблица переходов, б – таблица выходов.

Пример:

а) Таблица переходов                                        

x\q

q1

q2

q3

x1

q3

q1

q1

x2

q2

q3

q2

б) Таблица выходов

x\q

q1

q2

q3

x1

y1

y1

y2

x2

y1

y2

y1

Автомат Мура

Таблица переходов и таблица выходов объединяются, и добавляется строка
выходных сигналов, соответствующих состояниям автомата. На рисунке 4 показана таблица переходов и выходов для автомата Мура.

(qi,xk)

x\q

qi

.

.

.

xk

(qi,xk)

 .

.

.

Рис. 4. Таблица переходов и выходов

Пример. Таблица переходов и выходов:

y1

y 1

y 3

y 2

y 3

x\q

q1

q2

q3

q4

q5

x1

q2

q5

q5

q3

q3

x2

q4

q2

q2

q1

q1

2. Графовый способ  

Автомат представляется ориентированным связным графом (орграфом), вершины которого соответствуют состояниям автомата, а дуги – переходам из состояния
в состояние. Обозначения входных и выходных сигналов распределяются в автоматах Мили и Мура по-разному.

Построим графы для автоматов Мили и Мура по вышеприведенным таблицам:

Рис. 5. Представление автомата Мили в виде графа

Рис. 6. Представление автомата Мура в виде графа

Замечание: В автомате Мили выходной сигнал вырабатывается при переходе, а
в автомате Мура присутствует в течение всего периода дискретного времени, пока
автомат находится в данном состоянии.

Детерминированный автомат – автомат, в котором имеется полная определенность переходов из всех состояний в зависимости от входных сигналов (под действием одного и того же сигнала автомат не может переходить из любого рассматриваемого состояния в различные состояния). Фрагмент графа, изображенный на рисунке 7, не может относиться к детерминированному автомату.

Рис.7. Фрагмент графа, иллюстрирующий неопределенность переходов

Замечание: Недетерминированные (например, вероятностные) автоматы существуют, но их рассмотрение не предусмотрено в данном курсе.

Состояние автомата  qi  называется устойчивым, если для любого входного сигнала  хк , такого, что δ(qs , xk) = qi , справедливо соотношение: δ(qi , xk) = qi . (здесь qs – состояние, предшествующее qi). Это означает, что, автомат не изменяет своего состояния при повторении на следующем такте сигнала, приведшего его в состояние  qi . Фрагмент графа, иллюстрирующий устойчивость состояния, приведен на рисунке 8.

Рис. 8. Устойчивое состояние автомата

Автомат называется асинхронным, если каждое его состояние  qi  Q (i = 1, … , n) устойчиво; в противном случае автомат называется синхронным. Синхронные автоматы важны для теории, а на практике чаще используются асинхронные; устойчивость состояний в асинхронных автоматах достигается введением специальных сигналов синхронизации.

1.3. Примеры абстрактных автоматов, выполняющих полезные действия

1. Автомат для задержки сигнала на один такт (для запоминания на один такт)

Опишем данный автомат таблицами и графом:

Таблица переходов и таблица выходов:                         

x\q

q0

q1

x\q

q0

q1

x0

q0

q0

x0

y0

y1

x1

q1

q1

x1

y0

y1

                                                   

Поскольку автомат является двоичным, введем обозначения: x0 = y0 = 0; x1 = y1 = 1.

                                    

Рис. 9. Граф автомата для задержки сигнала на один такт

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

2. Автомат для проверки двоичной последовательности на четность.

Опишем данный автомат таблицами и графом:

Таблица переходов и таблица выходов:                         

x\q

q0

q1

x\q

q0

q1

x0

q0

q1

0

0

1

x1

q1

q0

1

1

0

Рис. 10. Граф автомата для проверки двоичной последовательности на четность

Анализ показывает, что «0» на выходе автоматически вырабатывается при четном числе единиц на входе, а «1» на выходе вырабатывается при нечетном числе единиц на входе.

Оба рассмотренных автомата имеют "слабую" память, но слабую в разном смысле.
У первого автомата "короткая" память во времени (помнит только один сигнал).
У второго автомата память "длинная" (длина входной последовательности может быть любой), но он различает (
распознает) лишь два класса последовательностей.

3. Автомат для задержки сигнала на два такта.

Автомат имеет четыре состояния, закодированных двумя двоичными разрядами:
q0 = 00; q1 = 01; q2 = 10; q3 = 11.

Рис. 11. Граф автомата для задержки сигнала на два такта

Достоинства примененного кодирования:

  •  первая цифра кода состояния показывает, какой сигнал выдает автомат (он легко преобразуется в автомат Мура); вторая цифра кода показывает, под действием какого сигнала автомат приходит в данное состояние.
  •  легко проверить, что выходной сигнал повторяет входной через два такта.

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

Автомат имеет два состояния: q0 – нет переноса (сложение цифр операндов не требует учета единицы переноса из предыдущего разряда кода);

q1 – есть перенос (единица переноса должна быть учтена).

         Рис. 12. Граф одноразрядного двоичного последовательного сумматора

В числителе "дроби", записанной при каждой из дуг графа, указаны цифры слагаемых; в знаменателе – результат суммирования в текущем разряде. Сумматор позволяет суммировать двоичные последовательности произвольной длины.

 1.4. Поведение изолированного синхронного автомата

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

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

   

 

Рис.13. Поведение изолированного синхронного автомата

Отметим, что длина цикла, измеренная числом дуг на диаграмме, не превышает числа состояний (n), то же самое можно сказать и о "времени" вхождения в цикл, измеренном в условных дискретных единицах.

Проблема умножения.

Теорема. Никакой конечный автомат не может перемножать пары чисел
с произвольно большим числом разрядов
.

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

Для математического доказательства используем метод "от противного": предположим, что существует автомат S, перемножающий пары двоичных чисел с произвольно большим числом разрядов (система счисления может быть любой без ограничения общности). Используем для опровержения последнего утверждения частный случай: оба сомножителя равны 2n . В этом случае каждый из сомножителей содержит единицу, за которой следуют n нулей; результат умножения (2n  2n = 22n) содержит единицу
и  2
n  нулей. Применим экономный способ использования памяти: пары разрядов сомножителей подаются последовательно, начиная с младших разрядов (аналогично тому, как это делалось в рассмотренном выше сумматоре).

Чтобы автомат правильно работал, он должен после прекращения подачи сомножителей добавить к уже выработанным  n + 1 нулям еще  n – 1  нулей, а затем в заключение единицу.  Но после прекращения подачи сомножителей автомат будет работать как изолированный.

Если изолированный автомат  S  имеет  k  состояний и способен выработать на выходе подряд  n  нулей, где n  k, то это означает, что он находится в поглощающем состоянии или вошел в цикл. Следовательно, он уже не сможет выработать единицу. Так как всегда возможно сделать значение  n  таким, что  n1  k , правильный результат при выполнении указанного неравенства не будет получен и, следовательно, предположение о существовании автомата  S  приводит к противоречию. Теорема доказана.

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

Рассмотрим структуру рекурсивных определений, которые применяются как средство строгого математического описания классов объектов. Рекурсивное определение некоторого класса   K  включают следующие части:

База – определяет один или несколько простейших объектов класса  К.

Рекурсия – состоит из одного или нескольких пунктов. В каждом пункте говорится, что если определенные виды объектов принадлежат классу  К , то и другие объекты, построенные из первых по некоторому правилу, также принадлежат классу К. Число пунктов рекурсии соответствует числу правил.

Ограничение – устанавливает, что никакие объекты, кроме тех, которые  построены посредством применения базы и рекурсии, не принадлежат классу  К.

Пример: рекурсивное определение правильного скобочного выражения (ПСВ).

БАЗА:  ( ) – ПСВ;

РЕКУРСИЯ:

а) если А – ПСВ и В – ПСВ, то АВ – ПСВ;

б) если А – ПСВ, то (А) – ПСВ;

ОГРАНИЧЕНИЕ: никаких других ПСВ нет.

Отметим, что в определении использованы метасимволы А и В, обозначающие
любые ПСВ; выражение
АВ обозначает конкатенацию (последовательную запись)
А и В.

Существует тесная связь между возможностями конечных автоматов и теми входными последовательностями, которые автомат распознает. Будем говорить, что автомат  S  распознает последовательность входных сигналов, если эта последовательность приводит к тому, что автомат переходит в заранее обусловленное состояние или выдает обусловленный выходной сигнал. Можно построить автомат, распознающий, например, слова некоторого языка, то есть отличающий "правильное" входное слово от недопустимого в данном языке входного слова.

Определим рекурсивно класс  R  регулярных выражений на заданном алфавите .

БАЗА: Любой однобуквенный символ  x    – регулярное выражение (x  R ).  

РЕКУРСИЯ:

а) если  E – регулярное выражение и  F – регулярное выражение, то  E  F
(выбор) – регулярное выражение  ((
E  F)  R );  

б) если  E – регулярное выражение и  F – регулярное выражение, то  EF – регулярное выражение  (EF  R );

  в) если  E – регулярное выражение, то и  E* – регулярное выражение (E*  R ).

ОГРАНИЧЕНИЕ: никаких других ПСВ нет.

В приведенном определении  E  и  F – метасимволы, обозначающие любые регулярные выражения; E* – любое число повторений  E, включая и отсутствие E. Приоритет введенных операций возрастает в порядке их перечисления.

Теорема Клини:

1. Конечный автомат может распознавать лишь регулярные множества последовательностей.

2. Любое регулярное множество последовательностей может быть распознано некоторым конечным автоматом.

Доказательство теоремы приведено в [1].

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

1.6. Алгоритмы и машины Тьюринга

В данном разделе рассматриваются более мощные (по сравнению с конечными автоматами) модели устройств, выполняющих вычисления, – машины Тьюринга (МТ). Анализ показал, что с помощью машин Тьюринга можно реализовать любой алгоритм. Одновременно МТ служит для уточнения самого понятия алгоритма и его формализации, поскольку, как установлено в теории вычислений, широко применяемые словесные определения алгоритма не являются точными и исчерпывающими.

Рассмотрим, например, следующее определение [2]: Алгоритм – это определенное на некотором языке конечное предписание (способ, рецепт), задающее дискретную
последовательность исполнимых элементарных операций для решения проблемы. Процесс выполнения предписания состоит из отдельных шагов, на каждом из которых выполняется одна очередная операция.

Как отмечено в  [2], это определение, понятное в интуитивном смысле, не является формальным. Употребленные в нем термины "предписание", "элементарная операция", а также объекты, к которым применяется алгоритм, требуют уточнения, если мы хотим говорить об алгоритмах строго. Алгоритмы в интуитивном смысле не являются математическими объектами, к ним не применимы формальные исследования и доказательства. Так, сравнение двух алгоритмов по эффективности, проверка их эквивалентности и т. д., возможны только на основе их формального представления.

Машина Тьюринга представляет собой бесконечный автомат, благодаря бесконечной (потенциально) ленте, разбитой на ячейки. В ячейках записываются символы некоторого алфавита МТ. Имеется также конечный автомат с головкой записи и считывания (ГЗЧ). ГЗЧ обозревает одну ячейку ленты в текущий момент дискретного времени.

Рис.14. Машина Тьюринга

Функции ГЗЧ: считывание символа из обозреваемой ячейки; запись символа
в обозреваемую ячейку; передвижение влево или вправо на одну ячейку.

В каждый момент времени МТ описывается следующей пятеркой:

(qi, sj, δ(qi, sj), λ(qi, sj), d(qi, sj)),

где

     qi – состояние МТ в текущий момент времени;

     sj – обозреваемый символ в текущий момент времени;

     δ – функция переходов, которая определяет следующее состояние;

     λ – функция выходов, определяющая запись нового символа в обозреваемую
ячейку;

     d – функция, определяющая передвижение головки влево (L) или вправо (R)
на один шаг.

Более краткое обозначение элементов пятерки: (qi , sj , qij , sij , dij).

Тезис Тьюринга: Любой процесс, который было бы естественно назвать
эффективной процедурой, может быть реализован МТ
.

Следует подчеркнуть, что тезис – это, в общем случае, правдоподобное утверждение, которое не обязательно математически строго доказано. Однако многие научные
тезисы действенны, так как прошли проверку временем и практикой.

Примеры машин Тьюринга для конкретных вычислений.

1. Счетчик четности единиц.

Рис.15.  МТ для счетчика четности

На рис. 15 показана МТ в начальном состоянии q0 , при этом обозревается первый символ двоичной последовательности, которая заканчивается ограничителем B. Далее на каждом такте ГЗЧ продвигается вправо, заменяя все символы символом "0", причем смена
состояний (
q0   на  q1  и обратно) происходит всякий раз, когда ГЗЧ обнаружит единицу. Таким образом, состояние  q0    связано с четным числом обнаруженных единиц, а состояние  q1  – с нечетным. Останов МТ (переход в заключительное состояние  H ) происходит по достижении символа B, при этом на его место записывается "0", если число единиц
в исходной последовательности было четным, и "1", если это число было нечетным.
После завершения процесса вычислений ГЗЧ будет указывать на эту ячейку с заключительной информацией, а во всех остальных ячейках ленты будут записаны нули.

Представим работу МТ двумя способами: таблицей и графом.

Строки таблицы содержат все "пятерки", описывающие функционирование МТ.

Таблица

qi

sj

qij

sij

dij

q0

0

q0

0

R

q0

1

q1

0

R

q0

В

Н

0

q1

0

q1

0

R

q1

1

q0

0

R

q1

В

Н

1

Рис. 16. Граф счетчика четности единиц

В вершинах графа явно указан символ, обозначающий движение ГЗЧ вправо в каждом из двух состояний. Заключительное состояние обозначено на рисунке буквой H – "halt" (останов).

2. Машина Тьюринга для проверки правильности скобочных выражений.

Рекурсивное определение правильного скобочного выражения (ПСВ) было дано
в разделе 1.3. Заметим, что конечный автомат не может решить поставленную задачу для скобочного выражения произвольной длины. МТ решает задачу в общем случае, так как наличие неограниченной ленты эквивалентно неограниченному объему памяти.

Рис. 17. МТ для проверки скобочных выражений

Скобочное выражение заключено между левым и правым ограничителями, обозначенными символом А. В начальном состоянии автомата ГЗЧ обозревает первый символ скобочного выражения (рис. 17). Реализация вычислений представлена графом (рис. 18).

Рис. 18.  Граф МТ для проверки скобочных выражений

Работа машины: сначала ГЗЧ движется вправо до первой правой скобки, заменяет ее символом X, переходит в состояние q1 и движется влево до ближайшей левой скобки, заменяет ее символом  X, переходит в состояние  q0 , и челночное движение повторяется.

Если машина, находясь в состоянии  q1, достигает левого символа  А, то печатает "0" и останавливается – скобочное выражение неправильно.

Если машина, находясь в состоянии q0, достигает правого символа А, не обнаружив больше правой скобки, то переходит в заключительное состояние q2, связанное с движением влево, и в последний раз просматривает последовательность: не осталась ли непарная левая скобка. Если по пути встретится левая скобка, то машина печатает "0" и останавливается. При достижении в состоянии  q2  левого символа А, машина печатает "1" и останавливается – скобочное выражение правильно.

3.  Машина Тьюринга для умножения двух чисел в унарном коде.

Действие машины представлено рисунками 19 – 21.

Рис. 19. МТ для умножения – исходное состояние

Рис. 20. МТ для умножения – результат операции

Рис. 21. Граф МТ – множительного устройства

На рис. 21 граф представлен в сокращенном виде –  не показаны петли с одинаковыми числителем и знаменателем.

МТ представляет собой простой базис для описания эффективных процедур,
поскольку все шаги, регламентирующие поведение автомата, определяются четкими правилами. В современной терминологии, МТ –  простой базис для описания алгоритмов и уточнения самого понятия алгоритма.

В приведенных выше примерах для каждого вычисления использовался свой специальный конечный автомат – так называемая конкретная машина Тьюринга. Конечный автомат в конкретных МТ играет роль алгоритма вычислений.

Можно считать, что любая МТ вычисляет некоторую функцию (заключительное содержимое ленты) от заданного аргумента (исходное содержимое ленты). В связи
с этим возникло понятие:
функция, вычислимая по Тьюрингу. 

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

УМТ имеет структуру, показанную на рис. 22.

Рис. 22. Структура УМТ

Левая часть ленты (до символа qi) имитирует ленту конкретной МТ, правая – содержит описание автомата конкретной МТ в виде пятерок.

Символ М показывает расположение ГЗЧ конкретной МТ; будем считать, что обозреваемый символ находится справа от символа М.

Пара ячеек qi, sj – зона режима, указывающая текущее состояние и текущий обозреваемый символ (на рисунке это символ "0").

Работа УМТ: УМТ начинает работу с запоминания символов  qi, sj  зоны режима, затем ГЗЧ движется вправо до тех пор, пока не найдет пятерку, в которой первые два символа совпадают с символами зоны режима. Найдя такую пятерку, УМТ запоминает qij, sij, dij , и ГЗЧ движется влево. Далее выполняются следующие действия:

  1.  qi : = qij , т. е. в зону режима записывается символ, обозначающий новое состояние автомата конкретной МТ;
  2.  справа от  М  записывается  sij ;
  3.  выполняется сдвиг М согласно значению dij (L или R), что соответствует передвижению ГЗЧ имитируемой машины;
  4.  запоминается новый обозреваемый символ (справа от М) и переносится
    в зону режима в качестве
    sj .

Таким образом, зона режима оказывается обновленной, и указанные действия повторяются до останова машины.

Вариант формулировки тезиса Тьюринга: Вычислимы те, и только те, объекты, которые могут быть вычислены УМТ.

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

В связи с этим возникает вопрос: существует ли универсальный распознаватель алгоритмов, т. е. МТ, которая для любой другой МТ определит, остановится последняя или нет. Этот вопрос назван в теории машин Тьюринга проблемой останова. Доказано, что проблема останова неразрешима и, следовательно, универсального распознавателя алгоритмов не существует [1]. Существуют и другие алгоритмически неразрешимые проблемы, к доказательству неразрешимости которых привлекается механизм вычислений, введенный Тьюрингом.

Простые системы (базисы) для решения проблем вычислимости создали независимо друг от друга и другие выдающиеся исследователи в области теории алгоритмов: А. Черч (математический аппарат рекурсивных функций), А. А. Марков (нормальные алгорифмы, сводящиеся к преобразованию слов в некотором алфавите), Э. Пост (механизм преобразования двоичных последовательностей, подобный МТ). Все названные системы равноценны с точки зрения их принципиальных возможностей и эквивалентны как формализмы для определения алгоритма [3].

1.7. Элементы теории формальных грамматик и языков

Основные определения

Алфавит –  множество символов, например,   = {a, b, c,…, z}.

Цепочка (слово) – последовательность символов из алфавита. Для обозначения цепочек используются строчные буквы латинского алфавита: α, β, γ … , а сами цепочки заключаются в ординарные кавычки. Например, = {a, b, c, =, –, +} – алфавит,
α = ‘
a + b = c’– цепочка над алфавитом; пустая цепочка  ε = ' ' – цепочка, не содержащая символов.

Рекурсивное определение цепочки над алфавитом :

БАЗА : ε – цепочка;

        РЕКУРСИЯ: если  x    и А – цепочка, то Ах – цепочка (здесь A – метасимвол, обозначающий любую цепочку);

ОГРАНИЧЕНИЕ: других цепочек нет.

Длина цепочки – число символов в цепочке, заключается в прямые скобки, например, |α| = 5,  |ε| = 0.

Подцепочка: цепочка β является подцепочкой цепочки α, если существуют такие цепочки γ и δ , быть может, пустые, что α = γ β δ .

Цепочка ‘победа’ содержит подцепочки: 'обед', 'беда', 'еда', 'да' (здесь цепочки заданы над алфавитом русского языка).

Конкатенация – сцепление цепочек; обозначается αβ или α·β. Конкатенация ассоциативна, но не коммутативна.

Обозначим через  * – множество всех цепочек над алфавитом  .

Система {*, · } образуют известную алгебру – полугруппу, в которой  * - носитель алгебры, ·  –  ассоциативная бинарная операция.

Обращение цепочки. Цепочка β называется обратной цепочкой цепочки α, если она представляет собой последовательность символов цепочки α, выписанных в обратном порядке.

Формальный язык 

Формальным языком L на алфавите    называется любое подмножество множества  * (L  *).

Примеры:

1) некоторые языки программирования, например, АЛГОЛ (с рядом оговорок);

2)   = {0, 1}, L = {α |, |α|  100} – множество цепочек в двоичном алфавите, длина которых не превышает 100 символов;

3)  L = {ε} – пустой язык;

4)  L = * ;

        5)    = {a, b, c}, α = {an bn cn | n  1}, здесь условный показатель n  при символе – число повторений символа.

Операции над языками. Поскольку языки – множества, к ним применимы известные теоретико-множественные операции, в частности, объединение языков (L1  L2) и пересечение языков (L1  L2).

Специфическая операция – конкатенация языков:

Пусть L1 – язык на  1 и  L2 – язык на  2, тогда конкатенация языков имеет вид:

L1 · L2 = {α β | α  L1, β  L2}

Способы задания языков:

1. Способ перечисления элементов; в искусственных языках не всегда удобен
из-за возможного большого числа элементов.

2. Способ задания с помощью характеристического свойства:

L = {α | Р(α)}, где  Р(α) –  предикат (характеристическое свойство множества).

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

  1.  Задание языков помощью допускающих (распознающих) автоматов.
  2.  Задание языков с помощью порождающих грамматик.

     Распознающий автомат выделяет из цепочек (слов), подаваемых на его вход, слова, принадлежащие определяемому языку.

      

входное слово                                       да (нет)

                                                                                           

Порождающая грамматика генерирует "правильные" цепочки, принадлежащие языку L.

                                                                   Генерирование цепочек языка

Далее предметом нашего рассмотрения будут порождающие грамматики.

Компонентами порождающих грамматик являются:

  1.  Два алфавита:

     - вспомогательный (нетерминальный);

     - основной (терминальный).

       Эти два алфавита не содержат общих символов, их пересечение пусто.

  1.  Множество правил вывода (продукций), состоящее из упорядоченных пар цепочек α, β. Каждая цепочка в этих парах составлена из объединения элементов терминального и нетерминального алфавитов. Сама продукция обозначается  α – –> β  и подразумевает замену при подходящих условиях цепочки  α   цепочкой  β.
  2.  Начальный символ (аксиома) грамматики – один из нетерминалов, который наделен особым статусом – с него начинается порождения языка.

Примем соглашение, касающееся обозначений в формальных грамматиках:

  •  малыми буквами начала латинского алфавита (a, b, c, …) обозначаются терминалы;
  •  большими буквами начала латинского алфавита (A, B, C, …) обозначаются нетерминалы;
  •  большими буквами конца латинского алфавита (U, V, W, X, Y, Z) обозначаются как терминалы, так и нетерминалы;
  •  греческими буквами (α, β, γ, …) обозначаются цепочки, которые состоят как из терминалов, так и нетерминалов;
  •  малыми буквами конца латинского алфавита (u, v, w, …) обозначаются цепочки, состоящие только из терминалов: именно они являются целевыми.

Порождающие грамматики общего типа (ПГОТ)

Обозначение грамматики: G = N, , P, S,

где:

N – нетерминальный алфавит;

– терминальный алфавит;

P – множество продукций; т. е. правил вывода вида   – –> β, где  α, β (N  )* ;

S – аксиома грамматики.

Пример 1. G1 = {S}, {a, b}, P, S,

где:

P:   1. aSa – –> aSb;

     2. S – –> a;

     3. S – –> aSa.

Непосредственная выводимость: цепочка β непосредственно выводима из цепочки α в грамматике G, если найдутся такие цепочки  γ1, γ2, 1, 2, что α = γ11γ2,
β = γ
12 γ2 , и среди правил вывода имеется правило  ω1 – –> ω2 .

В цепочке  α   подцепочки  γ1, γ2 контекст. Непосредственно выводимая цепочка получается применением одной продукции грамматики; обозначение непосредственной выводимости: α = => β. Примеры непосредственной выводимости в приведенной грамматике: aSa = => aSb; aSa = => aaa.

Знак «= =>» можно интерпретировать как обозначение бинарного отношения непосредственной выводимости.

Используя понятие непосредственной выводимости, определим выводимость.
Будем записывать: α = =>* β  (β  
выводима из  α), если существует последовательность
цепочек  α
0, α1, α2, … , αn , таких, что  α0 = α , αn = β  и  αi  = => αi+1 (i = 0, … , i-1 ), или
= . Указанную последовательность цепочек назовем выводом длины  n .

Таким образом, выводимость – рефлексивное и транзитивное бинарное отношение.

В рассмотренной грамматике G1 возможны выводы: S = =>* a (вывод длины 1);
S = =>* aaa  (вывод длины 2: S = =>* aSa = =>* aaa).

Язык, порождаемый грамматикой (обозначение – L(G)) – множество терминальных цепочек, выводимых из аксиомы, т. е. L(G) = {z  Σ* | S = =>* z}.

Пример 2. G2 = <N, Σ, P, S>;

N = {A, B, C, S}; S – аксиома;

Σ = {a, b, c};

P:  1. S – –> aSBC;

  2. S – –> abC

  3. CB – –> BC

  4. bB – –> bb

  5. bC – –> bc

  6. cC – –> cc         

Пример вывода: S = => aSBC = => aabCBC = => aabBCC = => aabbCC = =>
= =>
aabbcC = => aabbcc (здесь правила применены в порядке нумерации).

Грамматика  G2  порождает язык  L(G) = {an bn cn | n  1}.

Порождающие грамматики общего типа реализуются машинами Тьюринга.

В теории и практике разработки систем программирования, операционных систем, средств синтаксического анализа, компиляции и перевода применяются и другие
грамматики, например,
НС-грамматики (грамматики непосредственно составляющих),
КС-грамматики (контекстно-свободные грамматики), А-грамматики (автоматные грамматики).

Все известные грамматики являются частным случаем ПГОТ и получаются посредством ограничений, налагаемых на продукции.

Автоматные грамматики

Порождающая грамматика G = N, , P, S называется автоматной, если ее правило вывода имеет следующий вид:

 - правосторонние правила, или  - левосторонние правила,

где A, B  – элементы нетерминального алфавита; a – элемент терминального алфавита.

Языки, порождаемые А-грамматиками, называются регулярными языками (также языками Клини).

Пример 3: G3 = {S, A}, {a, b}, P, S>, где приняты правосторонние правила:

P:   1. S – –> aS;

     2. S – –> aA;

     3. A – –> bA;

     4. A – –> b.

Пример вывода: S = = > aS = = > aaA = = > aabA = = > aabb. В общем случае грамматика  G3 порождает язык  L(G3) = {an bm | n, m > 0}.

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

Иллюстрация связи между автоматными грамматиками и автоматами

Рассмотрим правостороннюю А-грамматику  G4 = N, , P, S :

N = {S1, S2, S3}, где S1 аксиома; Σ = {x, y, a, b}

      P: 1. S1 – –> ybS1

2. S1 – –> xaS2

3. S2 – –> xaS2

4. S2 – –> yaS3

 5. S3 – –> xbS1

Правила вывода включают входные терминальные символы x и y и выходные терминальные символы а и b.

Граф автомата Мили, реализующий данную грамматику, приведен на рис. 23.

Рис. 23. Граф, реализующий грамматику G4

Рисунок иллюстрирует следующие соответствия:

  •  нетерминалы соответствуют состояниям;
  •  терминалы соответствуют входным и выходным символам;
  •  продукции определяют переходы.

Полученный автомат является преобразователем входных слов в выходные. Так, слово 'yxyx' преобразуется в слово 'baab'. Множество выходных слов образует язык, который порождается данной грамматикой.

Взаимодействие автомата со средой

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

 x(t)         x(t)                                     y(t)        y(t)

 

Среду Е можно рассматривать как детерминированный или стохастический автомат, поведение которого зависит от его внутреннего состояния, внешних сигналов и времени.

Введем следующие обозначения:

y(t) – действия автомата;

х(t) – реакция среды;

х(t)= +1 – благоприятная реакция (выигрыш);

х(t)= -1 – неблагоприятная реакция (проигрыш).

В стационарной среде каждое действие автомата вызывает с вероятностью  pm  значение реакции  х(t)= -1 и с вероятностью  qm  значение  х(t)= +1. При этом, qm = 1 - pm ;
bm = qm - pm – оценка математического ожидания выигрыша за действие  ym .

Принято считать, что автомат обладает целесообразным поведением, если на множестве экспериментальных результатов (при различных соотношениях параметров qm  и  pm) математическое ожидание выигрыша М > М0, где М0 – математическое ожидание выигрыша при qm = pm = 0,5.

Исторически сложились такие направления исследований с применением моделирования:

Поведение автоматов в детерминированных и случайных средах.

Игры автоматов.

Коллективное поведение автоматов.

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

Большую роль в развитии фундаментальной теории автоматов сыграли такие исследователи, как Дж.фон Нейман, К. Шеннон, М. Л. Цетлин, В. М. Глушков, М. Минский.

Подходящим руководством для первоначального изучения теории формальных грамматик является книга М. Гросса и А. Лантена [4].

1.8. Условия автоматности отображения

Как уже отмечалось, автомат может рассматриваться как преобразователь слов
в алфавитах; однако не всякое преобразование слов может быть реализовано автоматом. Другими словами, не всякое отображение входных слов в выходные является
автоматным.

Условия автоматности отображения:

1. Отображение должно быть однозначным: каждому входному слову сопоставляется единственное выходное слово.

2. Область определения отображения должна удовлетворять условиям полноты. Это означает, что если в область определения входит некоторое слово, то и все его начальные отрезки также входят в область определения.

3. Отображение должно сохранять длину слова (каждое входное слово отображается в выходное слово той же длины).

4. Отображение должно переводить любой начальный отрезок входного слова
в начальный отрезок выходного слова той же длины.

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

  •  Операция выравнивания длин слов. Во входной и выходной алфавит добавляется по одной "пустой" букве (пропуск такта):  ε, δ, соответственно;

ε – приписывается один раз или многократно к концу входных слов,

δ – приписывается один раз или многократно к началу выходных слов.

В последовательной процедуре выравнивания на каждом шаге добавляется
                    не более чем по одной букве ε  и  δ, с последующей операцией пополнения.

  •  Операция пополнения. Применяется к выровненным отображениям и заключается в распространении отображения на начальные отрезки слов.

Пример: Проверим автоматность отображения:

   000 –> 001

   001 –> 011

Решение:

0 –> 0

00 –> 00

00 –> 01

Из двух последних строк следует, что отображение не однозначно.

Добавим по одной пустой букве к входным и выходным словам:

000ε –> δ001

001ε –> δ011

Проверим выполнение однозначности:

0 –> δ

00 –> δ0

00 –> δ00

001 –> δ01

Неоднозначность устранена – отображение удовлетворяет условиям автоматности.
В данном примере мы применили последовательную процедуру приведения отображения к автоматному, при этом оказалось достаточным однократное приписывание пустых букв к входным и выходным словам.

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

000 –> 001

001 –> 011 .

1.9. Построение графа автомата по входо-выходным последовательностям

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

Пусть дано отображение:

000 –> 000

001 –> 001

010 –> 010

011 –> 011

100 –> 110

101 –> 111.

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

Основной этап состоит из следующих шагов.

1. Построим граф в виде "ориентированного" дерева (рис.24); q0 – обозначение начальной  вершины, с которой начинается построение.

Рис. 24. Граф, представленный в виде дерева

2. Выделим и объединим одинаковые поддеревья путем склеивания вершин третьего яруса (рис. 25).

Рис. 25. Граф после склеивания вершин

4. Объединим (путем склеивания) вершины последнего яруса с начальной вершиной и введем идентификаторы состояний.

В результате получен граф автомата Мили, реализующий заданное отображение (рис. 26).

Рис. 26. Граф автомата Мили, реализующий заданное отображение

1.10. Преобразование автоматов

Два автомата называются эквивалентными, если они реализуют одинаковые отображения входных слов в выходные на всей области определения отображения. Автоматы Мили и Мура могут быть преобразованы друг в друга, т. е. для всякого автомата Мура может быть построен эквивалентный ему автомат Мили и, наоборот, для всякого автомата Мили – эквивалентный ему автомат Мура.

1. Преобразование автомата Мура в автомат Мили.

Пусть SА  – исходный автомат Мура; SB – автомат Мили, который является целью преобразования. Автомат Мура характеризуется шестиэлементным множеством:

SА = (XA, QA, YA, δA, λA, q1A)

Построим автомат Мили: SB = (XB, QB, YB, δB, λB, q1B).

Четыре первые компоненты автомата Мили, а также начальное состояние определяются исходя из равенств:

XB = XA,

QB = QA,

YB = YA,

δB = δA,

q1B = q1A.

Различие состоит в функциях выходов. Они определяются так: если в автомате Мура δA(qi, xj) = qs  и  yk = λA(qs), то в автомате Мили  λB(qi, xj) = yk (рис. 27).

Рис. 27. Фрагмент преобразования автомата Мура в автомат Мили

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

2. Преобразование автомата Мили в автомат Мура

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

SA = (XA, QA, YA, δA, λA, q1A) – исходный автомат Мили;

SB = (XB, QB, YB, δB, λB, q1B) – целевой автомат Мура.

Для алфавитов автомата  SB  будут справедливы следующие равенства:

XB = XA,

YB = YA.

Для определения множества  QB  каждому состоянию qs  QA поставим в соответствие множество  Qs  всевозможных пар вида  (qs, yt), где yt – выходной сигнал, приписанный дуге, входящей в qs.(фрагмент графа изображен на рис. 28).

Рис. 28. Вершина  qs  с входящими дугами

В этом случае Qs представляет собой множество пар вида:

Qs = {(qs, yl), (qs, y2), (qs, y3)}

В общем виде, если  D – множество дуг, входящих в вершину  qs , то  Qs определяется следующим образом:

Qs = {(qs, yt)| yt  D}

Итак, число элементов Qs равно числу различных выходных сигналов при дугах
автомата
SA, входящих в состояние qs . Множество состояний автомата SB получим как теоретико-множественное объединение множеств Qs , ассоциированных со всеми состояниями  qs  исходного автомата.

Вывод: число состояний в автомате Мура в среднем больше, чем число состояний в автомате Мили.

Функция  λB определяется так: каждому состоянию автомата SB, представляющему собой пару (qs, yt), ставится соответствие выходной сигнал  yt .

Функция  δB  определяется следующим образом: если в автомате Мили SA есть переход  δA(qi, xj) = qs и при этом выдается выходной сигнал  λA(qi, xj) = yp , то в автомате Мура SB будет переход из множества Qi состояний, порожденных состоянием qi , в состояние (qs, yp) под воздействием входного сигнала  xj  (рис. 29).

Рис. 29. Преобразование автомата Мили в автомат Мура

В качестве начального состояния q1B можно взять любое состояние из множества Q1, порожденного состоянием q1A.

ЗАДАЧИ И УПРАЖНЕНИЯ

1. Дать рекурсивное определение цепочки над некоторым алфавитом, используя понятия пустой цепочки и конкатенации.

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

           а) число единиц делится на 3;

           б) все единицы появляются сериями не менее чем из трех единиц;

           в) единица не появляется в момент времени, делящийся на 2 или 3.

3. Заменить регулярное выражение (a  b)* таким, в котором не используется
знак "
".

4. Совпадают ли множества последовательностей, представляемые регулярными выражениями  

  а) b(ab b)*a   и   bb*a(bb*a)* ;

  б) (a*ab ba)*a*  и  (a ab ba)* ?  

5. Какие из следующих равенств верны:

  а) E*F = (E  E*)*F ;

  б) E*F* = (E F)*(EF)* ;

  в) E*F* = E*EF* E*FF* ;

  г) E(FGE)*FG = EF(GEF)*G ?

Здесь E, F, G – метасимволы, обозначающие определенные последовательности символов алфавита.

6. Какие из следующих множеств последовательностей могут быть распознаны конечным автоматом:

  а) множество всех последовательностей: 0, 1, 00, 01, 10, 11, 000, 001, 010, … ;

  б) числа 1, 2, 4, 8, … , 2n, … , записанные в двоичной системе счисления;

  в) то же самое множество чисел, записанных в унарном коде: 1, 11, 1111, 11111111,
               1111111111111111, … ;

  г) множество последовательностей, в которых число нулей равно числу единиц;

  д) последовательности: 0, 101, 11011, … , 1k01k  (k – число повторений единицы)?   

Литература

  1.  Минский М. Вычисления и автоматы. – М.: Мир, 1971.- 364 с.
  2.  Карпов Ю. Г. Теория автоматов. – СПб.: Питер, 2002.- 206 с.
  3.  Кузнецов О. П., Адельсон-Вельский Г. М. Дискретная математика для инженера. – М.: Энергия, 1986.- 336 с.
  4.  Гросс М., Лантен А. Теория формальных грамматик. – М.: Мир, 1971.- 290 с.
  5.  Горбатов В. А. Основы дискретной математики. – М.: Высш. школа, 1984.- 310 с.


 

А также другие работы, которые могут Вас заинтересовать

63198. Київська Русь за Володимира Мономаха 25.89 KB
  Мета: характеризувати процес посилення великокнязівської влади за Володимира Мономаха та довести що за його правління Київська Русь зазнає періоду піднесення; розвивати в учнів уміння давати характеристику історичному...
63200. Роздробленість Київської Русі, політична роздробленість 27.35 KB
  Сизначати причини роздробленості Київської Русі її сутність та наслідки; розвивати в учнів уміння встановлювати причинно-наслідкові звязки працювати з джерелами інформації аналізувати історичний матеріал...
63201. Захист особистих немайнових і майнових прав 28.06 KB
  Мета: сформувати в учнів поняття про особисті немайнові та майнові права навчити їх розрізняти; розвивати вміння аналізувати ситуації і правильно їх оцінювати; виховувати в учнів розуміння цінності особи необхідності поваги і дотримання її прав.
63202. Політичний і соціально-економічний розвиток Київського, Чернігово-Сіверського та Переяславського князівств у середині XII - першій половині XIII століття 35.58 KB
  Київське князівство Географічне положення Київське князівство полянське Правобережжя землі древлян південнозахідні райони розселення дреговичів а також землі уличів у басейні Південного Бугу.
63205. Цивільно-правова відповідальність 24.03 KB
  Мета: ознайомити учнів з особливостями та порядком притягнення до цивільноправової відповідальності; сформувати розуміння можливої відповідальності за завдану шкоду; виховувати почуття відповідальності за свої дії.