Общее понятие автомата

----------------

011 000

1001 0011

T ₉ применим ко всем 8 словам длины 3 в алфавите {0, 1} и задаётся таблицей

x | 000 001 010 011 100 101 110 111

-----------------------------------------------

T ₉ x | 000 000 010 011 000 001 000 001

Общее понятие автомата

Ранее мы договорились называть алгеброй всякое непустое множество вместе с каким-либо фиксированным набором операций на нём.

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

Допустим, по каким-либо причинам нас заинтересовала пятёрка = (Q, X, Y; Y, F), где: Q, X, Y — некоторые непустые множества; Y — некоторое отображение Q ´ X в Q; F — некоторое отображение Q ´ X в Y. Такая пятёрка — частный пример многоосновной алгебры, а именно, трёхосновной алгебры сигнатуры (Y⁽²⁾, F⁽²⁾) с носителями Q, X, Y.

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

С другой стороны, в зависимости от характера интереса мы вправе пятёркам вида (Q, X, Y; Y, F) присваивать специальные названия, дабы подчеркнуть специфику нашего интереса.

Именно так дело и обстоит в теории автоматов. Теория автоматов — это как раз некоторый специфический интерес к алгебрам вида M, и любая такая алгебра называется автоматом, если она рассматривается в рамках этого интереса.

Таким образом, мы имеем определение: автомат — это произвольная пятёрка (произвольная трёх основная алгебра) указанного вида M.

При этом по историческим причинам, которые будут объяснены в нужный момент, множества (носители) Q, X, Y алгебры M называются соответственно внутренним, входным и выходным алфавитами, элементы этих множеств называются символами соответствующих алфавитов, отображение Y: Q ´ X ® Q называется функцией переходов, а отображение F: Q ´ X ® Y называется функцией выходов.

Кроме того, принято символы входного алфавита X называть входными, символы выходного алфавита Y — выходными символами, символы внутреннего алфавита Q состояниями (внутренними) автомата.

Всевозможные четвёрки (q, x, Y (q, x), F (q, x)) называют командами автомата; команды будем записывать ещё и так: qx ® Y (q, x) F (q, x).

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

Пусть зафиксировано некоторое состояние q ₀ автомата M = (Q, X, Y; Y, F). Тогда рекуррентные соотношения

q (t + 1) = Y [ q (t), x (t)],

y (t) = F [ q (t), x (t)], (1)

где q (t), q (t + 1) Î Q, x (t) Î X, y (t) Î Y, дополненные начальным условием

q (1) = q ₀,

задают оператор (обозначим его через T (M, q ₀)), который преобразует всякую конечную последовательность входных символов

x = x (1) x (2) x (3) … x (r)

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

y = T x = y (1) y (2) y (3) … y (r).

Заметим, что последовательности x и y записывается здесь нестандартным образом: опускаются скобки и запятые

Пару (M, q ₀) назовём инициальным автоматом и будем говорить, что инициальный автомат (M, q ₀) реализует оператор T (,M q ₀) или, что то же самое, что оператор T (M, q ₀) является поведением инициального автомата (M, q ₀).

Будем говорить, что автомат M реализует оператор T, если при некоторой подходящей фиксации начального состояния q ₀

T = T (M, q ₀).

Очевидно, что в соответствии с этим определением один и тот же автомат M реализует, вообще говоря, много различных операторов T, которые в совокупности составляют множество { T | T = T (M, q ₀), q ₀ Î Q }.

Введём ещё несколько терминов.

Конечные непустые последовательности символов из некоторого алфавита A назовём словами в алфавите A (в литературе встречаются и другие термины-синонимы: цепочка в A, лента в A), а любое множество слов в алфавите A — языком в A (синонимы: событие в A, множество лент в A).

Слова в Q, X, Y будем называть соответственно внутренними, входными и выходными словами.

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

В этих терминах, оператор T (M, q ₀) перерабатывает слова (входные) x = x (1) x (2) x (3) … x (r) в слова (выходные) y = y (1) y (2) y (3) … y (r).

Такие операторы можно называть словарными операторами.

Ясно, однако, что мы могли бы охарактеризовать поведение инициального автомата и посредством сверхсловарного оператора, т.е. такого оператора, который перерабатывает сверхслова (а именно входные сверхлова) в сверхслова (выходные).

В самом деле, каково бы ни было входное сверхслово x = x (1) x (2) x (3) …, рекуррентные соотношения (1), дополненные начальным условием q (1) = q ₀, однозначно определяют сверхслово T x = y = y (1) y (2) y (3) ….

Легко понять, что словарное поведение инициального автомата (M, q ₀) и сверхсловарное его поведение тесно связаны друг с другом и однозначно восстанавливаются одно по другому.

Благодаря этому не очень существенно, что подразумевается под оператором T (M, q ₀): словарный или сверхсловарный оператор.

Теперь обещанные исторические причины того, почему всё названо так, как названо.

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

Входной канал воспринимает (считывает) входные сигналы из внешней среды, а выходной канал выдаёт выходные сигналы во внешнюю среду.

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

А раз так, то их стали рассматривать как некие символы (буквы), образующие соответственно алфавит состояний (или внутренний алфавит) Q, входной алфавит X и выходной алфавит Y.

Точно так же, первоначально работу автомата считали протекающей в дискретные такты времени t = 1, 2, 3, …; потом обобщили это временное представление о работе, став считать, что временная природа целочисленной величины t вовсе не обязательно. Важно лишь то, что t = 1, 2, 3, ….

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

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

Важно не то, как что называется, а то, какой названия имеют смысл.

Мы познакомились с несколькими терминами теории автоматов. Ниже следует дополнительное пояснение («разжевывание») этих терминов.

Итак, первый термин — автомат. Автомат M, согласно определению, — это просто любая пятёрка вида (Q, X, Y; Y, F), где: Q, X, Y — некоторые множества; Y — некоторое отображение Q ´ X в Q; F — некоторое отображение Q ´ X в Y. Вот такая пятерка — и ничего более.

Иными словами, задать конкретный автомат M = (Q, X, Y; Y, F) означает в точности то же самое, что задать конкретное множество Q, конкретное множество X, конкретное множество X, конкретное отображение Y: Q ´ X ® Q, конкретное отображение F: Q ´ X ® Y, и считать все эти заданные вещи членами пятёрки указанного вида.

При этом не плохо иметь в виду, что отображения Y и F — это тоже множества, и что смысл слова «задать» применительно к множествам может быть сугубо свой для каждого из множеств Q, X, Y, Y, F. Кроме того, все эти смыслы могут меняться от ситуации к ситуации. Так что, смысл слова «задать» применительно ко всему автомату M = (Q, X, Y; Y, F) понятен нам, так сказать, по модулю понимания смыслов этого слова применительно к упомянутым множествам и ситуациям.

В частности, если все множества Q, X, Y конечны, то мы можем задать каждое из них простым списком их элементов. Например, Q = {1, 2, 3}, X = { a, b }, Y = { a, b, c }. Отображение Y можно задать Таблицей 1а:

Y (q, x)

1 2 3

a 3 3 1

b 2 3 3.

Отображение F можно задать Таблицей 1б:

F (q, x)

1 2 3

a b a b

b c c c.

Этот же самый автомат можно задать и иначе. Например, построим следующее электромеханическое устройство. У него есть тумблер, который может находиться в одном из следующих трех положений: 1, 2, 3. у него есть две кнопки, помеченные буквами a, b, и три лампочки, помеченные буквами a, b, c. Множество возможных положений тумблера объявляем множеством Q, множество букв на кнопках — множеством X, множество букв на лампочках — множеством Y. Очевидно, как и в первом примере, Q = {1, 2, 3}, X = { a, b }, Y = { a, b, c }. Устройство спроектировано так, что если тумблер находится в положении1, и мы нажали и отпустили кнопку с буквой a, то вспыхивает и гаснет лампочка с буквой b, и, кроме того, тумблер перескакивает в положение 3 и в нём остаётся. Мы говорим в этом случае, что Y (1, a) = 3, F (1, a) = b.

Если тумблер находится в положении 1, и мы нажали и отпустили кнопку с буквой b, то вспыхивает и гаснет лампочка с буквой c, и, кроме того, тумблер перескакивает в положение 2 и в нём остаётся. Говорим в этом случае, что Y (1, b) = 2, F (1, b) = c.

Если тумблер находится в положении 2, и мы нажали и отпустили кнопку с буквой a, то вспыхивает и гаснет лампочка с буквой a, и, кроме того, тумблер перескакивает в положение 3 и в нём остаётся. Говорим в этом случае, что Y (2, a) = 3, F (2, a) = a.

Если тумблер находится в положении 2, и мы нажали и отпустили кнопку с буквой b, то вспыхивает и гаснет лампочка с буквой c, и, кроме того, тумблер перескакивает в положение 3 и в нём остаётся. Говорим в этом случае, что Y (2, b) = 3, F (2, b) = c.

Если тумблер находится в положении 3, и мы нажали и отпустили кнопку с буквой a, то вспыхивает и гаснет лампочка с буквой b, и, кроме того, тумблер перескакивает в положение 1 и в нём остаётся. Говорим в этом случае, что Y (3, a) = 1, F (3, a) = b.

Если тумблер находится в положении 3, и мы нажали и отпустили кнопку с буквой b, то вспыхивает и гаснет лампочка с буквой c, и, кроме того, тумблер перескакивает в положение 3 и в нём остаётся. Говорим в этом случае, что Y (3, b) = 3, F (3, b) = c.

Таким образом, автомат M задан в виде ({1, 2, 3}, { a, b }, { a, b, c }; …).

Между прочим, это третий способ задания, или, как ещё говорят, третья репрезентация, или представление автомата.

Теперь рассмотрим способ представления слов и сверхслов.

Пусть A — произвольное непустое множество, которое иногда мы позволяем себе называть алфавитом. Тогда произвольная конечная последовательность a = (a ₁, a ₂, …, a _r) длины r называется словом в алфавите A, если и только если все её члены — элементы (символы) множества (алфавита) A.

Даже если алфавит A конечен (например, содержит один символ), множество A * всех слов в нём является счётным.

Например, пусть A = { a }. Тогда (a), (a, a), (a, a, a) и т.д.— слова в A длины 1, 2, 3 и т.д., соответственно.

Или пусть A = { a, b }. Тогда слова в A — это, в частности, (a), (b), (a, a), (a, b), (b, a), (b, b) и т.д.

Иногда слово a = (a ₁, a ₂, …, a _r) длины r в алфавите A обозначают так: a = a (1) a (2) … a (r), подразумевая при этом, что a (1) = a ₁, a (2) = a ₂, …, a (r) = a _r.

Например, в алфавите A = { a } слово (a) обозначается как a (1), слово (a, a) — как a (1) a (2) и т.д.

В алфавите A = { a, b }слово (a) обозначается как a (1), и слово (b) обозначается как a (1), слово (a, a) обозначается как a (1) a (2), и слово (a, b) обозначается (a, b), и т.д.

Мы видим, что при такой системе записи разные слова имеют одинаковые обозначения. Поэтому нужно всякий раз учитывать, что же каждый раз молча подразумевается. Когда мы обозначаем через a (1) a (2) слово (a, a), то подразумеваются равенства: a (1) = a, a (2) = a. А когда мы обозначаем через a (1) a (2) слово (a, b), то подразумеваются равенства: a (1) = a, a (2) = b.

Помимо всего этого, нужно учитывать смысл, в каком мы говорим, что задана последовательность a = (a ₁, a ₂, …, a _r) в том или ином алфавите A.

Например, если A = X = { a, b }, где X — множество, заданное вышеприведённым электромеханическим устройством, то последовательность (a, a) — это нажатие друг за другом кнопки с буквой a, а последовательность (a, b) — это нажатие сначала кнопки с буквой a, а затем кнопки с буквой b.

Пойдём дальше.

Пусть A и B — алфавиты. Тогда всякое отображение T: A * ® B * называется словарным оператором из A * в B *.

Если b = T a, то мы говорим, что слово a переводится, перерабатывается, преобразуется оператором T в слово b, и записываем это также, в виде a ↦ T a = b или просто a ↦ b, если T подразумевается.

Если A — алфавит, то любая бесконечная последовательность a = (a ₁, a ₂, …) элементов из A называется сверхсловом в A. Множество всех сверхслов в алфавите A договоримся обозначать через A **.

Для сверхслов справедливы все те же приёмы обозначений, что и для слов. В частности, всякое отображение T: A ** ® B ** называется сверхсловарным оператором из A ** в B **.

Пусть теперь зафиксировано некоторое состояние q ₀ автомата M = (Q, X, Y; Y, F). Тогда рекуррентные соотношения

q (t + 1) = Y [ q (t), x (t)],

y (t) = F [ q (t), x (t)], (1)

где t = 1, 2, 3, …, и начальное условие

q (1) = q ₀, (2)

задают словарный оператор T: X * ® Y * (обозначим его через T (M, q ₀)), который преобразует всякую конечную последовательность входных символов

x = x (1) x (2) x (3) … x (r)

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

y = T (M, q ₀) x = y (1) y (2) y (3) … y (r).

Причём, y (1) = F [ q ₀, x (1)]

Пару (M, q ₀) назовём инициальным автоматом и говорим, что инициальный автомат (M, q ₀) реализует словарный оператор T: X * ® Y *, задаваемый соотношениями (1) и (2) или, что то же самое, что оператор T (M, q ₀) является словарным поведением инициального автомата. (M, q ₀).

Осталось заметить, что те же самые соотношения (1) и (2) задают соответствующий сверхсловарный оператор T: X ** ® Y ** (обозначим его также T (M, q ₀)). Он называется сверхсловарным поведением инициального автомата (M, q ₀).

В тех случаях, когда нам не важно, о каком поведении — словарном или сверхсловарном — идёт речь, мы просто говорим, что T (M, q ₀) является поведением инициального автомата (M, q ₀).

И, наконец, мы говорим, что автомат M реализует оператор T, если при некоторой подходящей фиксации начального состояния q ₀, T = T (M, q ₀).

КОНЕЦ

Лекция 4