Представление языков и сверхъязыков в автоматах

1. Параметры потока заявок на обслуживание в СМО с потерями.

2. Какие свойства СМО с потерями вам известны?

3. Перечислить основные показатели качества обслуживания абонентов на телефонной станции.

Задание на самостоятельную работу и литература:

проработать самостоятельно учебный материал по литературе [1, 2], дополнить конспект, перенести в него все показанные слайды, изучить плакаты по теме лекции, добиться полного уяснения и усвоения учебного материала занятия.

Доцент кафедры № 42 Г.Г.Меженцев

Представление языков и сверхъязыков в автоматах

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

В самом деле, пусть A — язык в алфавите X, насчитывающем m букв. Представляющий автомат (M, q ₀, Q ¢) можно, в частности выбрать так: диаграмма автомата является бесконечным деревом, из каждой вершины которого выходит в точности m рёбер, помеченных входными буквами.

Корень этого дерева изображает начальное состояние q ₀.

Далее, к множеству Q ¢ относятся все такие и только такие состояния q, для которых в A найдётся слово p, переводящее q ₀ в q.

Слишком широким (для любых разумных целей) является и класс всех сверхъязыков, представимых в автоматах (опять-таки имеется в виду — в любых автоматах и при любой макронастройке).

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

К таким классам относится класс w всех языков, представимых в конечных автоматах (конечно - автоматных языков), и класс W всех сверхъязыков, представимых в конечных автоматах (конечно - автоматных сверхъязыков).

Некоторое представление о классах w и W дают приводимые ниже примеры.

Пример 1. Всякий язык, состоящий из единственного слова x = x (1) x (2) x (3) … x (r), конечно - автоматен. Представляющий автомат можно строить с r + 2 состояниями q _1, …, q _r, q _r+1, q _r+2, из которых q ₁ — начальное, q _r+1 — единственное финальное состояние. Команды автомата таковы: q ₁ x (1) → q ₂, …, q _r x (r) → q _r+1, и, кроме того, для любой пары q _a x _b, отличной от каждой из левых частей только что перечисленных команд, имеется команда q _a x _b → q _r+2.

Состояние q _r+2, подчеркнём, обладает тем свойством, что любая входная буква (а значит, и любое входное слово) переводит его опять в q _r+2 (т.е. в то же самое состояние). Состояния, обладающие таким свойством, условимся называть тупиковыми.

Пример 2. Всякий сверхъязык, состоящий из единственного периодического сверхслова x = x (1) x (2) x (3) … x (r) x (r+1) x (r+2) … x (r+s) … с предпериодом x (1) x (2) x (3) … x (r) и периодически повторяющейся частью x (r+1) … x (r+s), конечно-автоматен. Представляющий автомат можно построить с r+s+1 состояниями q _1, …, q _r, q _r+1, …, q _r+s, q _r+s+1, из которых q ₁ объявляется начальным. В качестве единственного предельного макросостояния взято множество { q _r+1, …, q _r+s}, а команды таковы:

q _i x (i) → q _i+1 (i < s + r),

q _r+s x (r+s) → q _r+1,

и, кроме того, вводим для пар q _a x _b, не встречающихся в левых частях перечисленных команд, команды q _a x _b → q _r+s+1 (т.е. q _r+s+1 является тупиковым состоянием).

Пример 3.

а) б)

Рис. 11.

Всякий конечный язык конечно-автоматен. Представляющий автомат удобнее сразу задать его диаграммой.

Ограничимся иллюстрацией для языка A = {00, 01, 1, 111}.

Строим конечное дерево для этого множества слов, как это показано на рис 11, а), где каждая жирная вершина соответствует одному из слов языка A.

Далее, это дерево дополняется до диаграммы ведением новой вершины, в которую направляются все недостающие рёбра (см. рис 11, б, где пары «параллельных» рёбер заменены одним ребром).

Корень дерева изображает начальное состояние, а жирные вершины — финальные состояния.

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

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

Сначала мы рассмотрим здесь теоретико-множественные операции: сумму (объединение) È, пересечение Ç, дополнение Ø, проекцию и цилиндр.

Первые три операции определяются обычным образом. Приведём определения последних двух.

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

Пусть, например, X = X ₁ ´ …´ X _m. Это означает, что буквами алфавита X объявляются всевозможные последовательности вида (x ₁ … x _m), где x _i Î X _i, i £ m. Если x — буква в алфавите X, то её проекцией в алфавите X_{s 1} ´ …´ X _sm (s1 < … < sm) называется буква (x _{s 1} … x _sm); проекцией же слова называется слово образованное, из соответствующих проекций отдельных его букв.

В частности, для каждого слова

(x (1) y (1)) (x (2) y (2)) … (x (t) y (t))

в алфавите X ´ Y его проекциями в X и в Y (его X- и Y – проекциями) называются слова

x (1) … x (t) и y (1) … y (t)

соответственно.

Аналогично определяются проекции сверхслова.

Произведения алфавитов особенно часто встречаются в структурной теории автоматов; например, наличие входного алфавита X = X ₁ ´ …´ X _m интерпретируется как наличие у автомата m входных каналов, по каждому из которых воспринимается соответствующая проекция входной информации.

В качестве иллюстрации и в качестве намёка на то, чем занимается структурная теория автоматов, укажем две простейшие операции над автоматами.

Для двух автоматов

M ¢ = (Q ¢, X ¢, Y ¢; Y ¢, F ¢) и M ¢¢ = (Q ¢¢, X ¢¢, Y ¢¢; Y ¢¢, F ¢¢)

Определим их (декартово) произведение

M = (Q, X, Y; Y, F)

условиями (рис 12, а):

а) б)

Рис. 12.

Q = Q ¢ ´ Q ¢¢, X = X ¢ ´ X ¢¢, Y = Y ¢ ´ Y ¢¢;

Для всякой пары команд

q ¢_i x ¢_r → q ¢_v y ¢_s

и

q ¢¢_j x ¢¢_r → q ¢¢_m y ¢¢_s

из M ¢ и M ¢¢ соответственно в M имеется команда

(q ¢_i q ¢¢_j)(x ¢_r x _r )→ (q ¢_v q ¢¢_m)(y ¢_s y ¢¢_s).

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

Если M ¢ и M ¢¢ и имеют общий входной алфавит (X ¢ = X ¢¢), то можно рассматривать родственную операцию — произведение с отождествлением входов.

Для простоты определим её для случая, когда M ¢ и M ¢¢ (а значит, и результирующий автомат M) — автоматы без выхода (рпс.12, б):

M = (Q, X; Y,),

где X = X ¢ = X ¢¢, Q = Q ¢ ´ Q ¢¢ и для всякой пары команд

q ¢_i x _l → q ¢_v

и

q ¢¢_j x _l → q ¢¢_m

соответственно из M¢ и M¢¢ в M имеется команда

(q ¢_i q ¢¢_j) x _l→ (q ¢_v q ¢¢_m).

КОНЕЦ

Лекция 12

Вернёмся к языкам.

Пусть задан язык (сверхъязык) A в алфавите X ´ Y. Проекцией в X (X – проекцией) языка (сверхязыка) A называется язык (сверхъязык), состоящий в точности из проекций в X слов (сверхъслов) языка (сверхъязыка) A.

Пусть заданы алфавит Y и язык (сверхъязык) A в алфавите X. Y - цилиндром языка (сверхъязыка) A называется язык (сверхъязык) B, состоящий из всех слов (сверхъслов) в алфавите X ´ Y, X - проекции которых принадлежат X.

Для перечисленных операций справедлива теорема 1.1., которая формулируется и доказывается совершенно аналогично для языков и сверхъязыков.

ТЕОРЕМА 1. Существуют алгоритмы, которые:

(I) по заданному конечному автомату (M, q ₀, Q) ((M, q ₀,C)) строят конечный автомат, представляющий язык Ø w (M, q ₀, Q)(сверхъязык Ø W (M, q₀,C));

(II) по заданным (M ¢, q ¢₀, Q ¢) и (M ¢¢, q ¢¢₀, Q ¢¢) ((M ¢, q ¢ ₀,C¢) и (M ¢¢, q ¢¢₀,C¢¢)) с общим алфавитом X строят конечный автомат (M, q ₀, Q) ((M, q ₀,C)), представляющий язык w(M ¢, q ¢₀, Q ¢) È w (M ¢¢, q ¢¢₀, Q ¢¢) (сверхъязык W (M ¢, q ¢ ₀,C¢) È W (M ¢¢, q ¢¢₀,C¢¢));

(III) по заданному конечному автомату (M, q ₀, Q) ((M, q ₀,C)) и алфавиту Y строят конечный автомат (R, q ₀, Q) ((R, q ₀,C)), представляющий Y - цилиндр языка w(W, q ₀, Q) (сверхъязыка W (M, q₀,C)).

ДОКАЗАТЕЛЬСТВО. Ограничимся случаем для сверхъязыков. Утверждение (I) совершенно очевидно, ибо достаточно в заданном автомате заменить C на множество тех непустых макросостояний, которые не вошли в C. Что же касается макронастроенного автомата (M, q ₀,C) из (II), то он строится следующим образом. Автомат M является декартовым произведением автоматов M ¢, M ¢¢ с отождествлением входов. Начальным состоянием q ₀ объявляем (q ₀ q ¢¢₀). Рассмотрим теперь какое-нибудь макросостояние R автомата M. Множество всех тех состояний автомата M ¢, которые встречаются в качестве первых элементов пар из R, образуют проекцию в M ¢; обозначим это множество (эту проекцию) через R¢. Аналогично можно рассматривать множество R¢¢, являющееся соответствующей проекцией макросостояния R в M ¢¢. Макросостояние R отнесём к C тогда и только тогда, когда выполняется условие: R¢ Î C¢ или R¢¢Î C¢¢. Этим завершается построение макронастроенного автомата (M, q ₀,C). Очевидно, что W (M, q₀,C) в точности совпадает с

W (M ¢, q ¢ ₀,C¢) È W (M ¢¢, q ¢¢₀,C¢¢).

(III) Автомат (M, q ₀,C), представляющий сверхъязык A в алфавите X, можно перестроить в автомат (R, q ₀,C), представляющий соответствующий Y - цилиндр, при помощи следующей процедуры введения кратных рёбер. В диаграмме R вершины те же, что и в диаграмме M. Если в M из q _i в q _j ведёт ребро, помеченное буквой x _k, то в R из q _i в q _j для каждой буквы y _i Î Y проводится ребро, помеченное парой (x _k y _i). Предельные макросостояния остаются прежними. Теорема доказана.

Отметим, что из доказательства немедленно усматриваются следующие оценки для числа состояний результирующего конечного автомата (по сравнению с числом состояний в исходных конечных атоматах): цилиндр не увеличивает число состояний; суммирование (объединение) требует не более, чем произведения чисел состояний заданных автоматов.

Далее, подчеркнём, что поскольку пересечение A ₁ Ç A ₂ выразимо через сумму и дополнение:

A ₁ Ç A ₂ = Ø(Ø A ₁ È Ø A ₂),

то класс конечно-автоматных языков (сверхъязыков) замкнут и относительно операции пересечения, причём с такой же оценкой числа состояний, как и для суммы.

ЗАМЕЧАНИЕ1. Теорема 1 не затрагивает вопроса о замкнутости относительно проекции. Этот вопрос значительно труднее и требует особого рассмотрения, на которое у нас нет времени. Но если бы мы его провели, то получили бы усиление теоремы1, говорящее о том, что класс конечно-автоматных языков (сверхъязыков) замкнут также относительно проекции. Более того, на самом деле в теории автоматов доказаны теоремы, говорящие о замкнутости конечно-автоматных языков и сверхъязыков относительно многих других операций. Однако все эти теоремы довольно сложны и не рассматриваются в пределах настоящего курса лекций.

КОНЕЦ

Лекция 13