• Название:

    Лекции 5 6


  • Размер: 0.14 Мб
  • Формат: RTF
  • или
  • Сообщить о нарушении / Abuse

    Осталось ждать: 10 сек.

Установите безопасный браузер



Предпросмотр документа

Лекция 5

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

Пока мы рассмотрели только те разновидности концепций автоматов, которые возникают из концепции автомата общего типа путём наложения ограничений на мощности алфавитов Q, X, Y. Но, ведь, можно классифицировать автоматы по различным ограничениям на функции .

Так вот, если мы хотим классифицировать автоматы именно так, то автомат общего вида M = (Q, X, Y; , когда на функции не накладываются никакие специальные ограничения, называют автоматом Мили.

Если функция выходов имеет вид q), т.е. она не зависит от x, то автомат M = (Q, X, Y; называют автоматом с задержкой.

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

Автомат Мура характеризуется следующей связью между функциями и : q, x = (q, x), где — так называемая сдвинутая функция выходов, т.е. просто некоторое отображение Q в Y.

Таким образом, различие между автоматами с задержкой и автоматами Мура заключается лишь в том, что, при наличии общего для тех и других рекуррентного соотношения q(t + 1) = q(t), x(t), для первых

y(t) = q(t),

а для вторых

y(t) = q(t + 1).

(Почему?).

Заметим, что при данных алфавитах Q = {{ q1, , qk, X = {{ x1, , x m и Y = {{ y1, , y n число автоматов с задержкой, так же как и число автоматов Мура, равно kmk nk.

Ещё одно замечание.

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

Что касается а.б.п., то его поведением является такой простой и прозрачный объект, как истинностный оператор.

Поведение ав.а. характеризуется одним выходным сверхсловом и одним внутренним сверхсловом (почему?); если ав.а. конечен, то каждое из этих сверхслов периодично (как сказать точнее? почему?) и опять-таки мы имеем дело с очень простыми объектами.

Положение становится иным, когда речь идёт о поведении а.б.в., пусть даже и конечного.

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

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

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

По этой причине мы не будем в дальнейшем специально изучать а.б.п. и ав.а., но уделим достаточное внимание изучению а.б.в.

Может ли быть а.б.в. автоматом с задержкой? Автоматом Мура? Автоматом Мили?

КОНЕЦ

Лекция 6

§3. Автоматы и графы

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

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

Если вы посмотрите статью Граф в «Математической энциклопедии», выпущенной в 1997 г., то там вы обнаружите следующие определения.

«Граф — множество V вершин и набор E неупорядоченных и упорядоченных пар вершин; обозначается Г. через G(V, E). Неупорядоченная пара вершин наз. ребром, упорядоченная пара — дугой. Г., содержащий только рёбра, наз. неориентированным; Г., содержащий только дуги, — ориентированным. Пара вершин может соединяться двумя или более рёбрами (дугами одного направления), такие рёбра (дуги) наз. кратными. Дуга (или ребро) может начинаться и кончаться в одной и той же вершине, такая дуга (ребро) наз. петлёй. (иногда под Г. понимают Г. без петель и кратных рёбер; тогда Г., в к-ром допускаются кратные рёбра, наз. мультиграфом, а Г., в к-ром допускаются кратные рёбра и петли, наз. псевдографом).»

Хотя эти определения приведены в указанной Энциклопедии, они никуда не годятся. (Почему?).

Поэтому мы будем пользоваться другой терминологией.

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

Именно, дан граф

L = (X, U; P),

если даны: множество X ; множество U такое, что X U = ; тернарное отношение P X U X, удовлетворяющее следующему условию Б:

Б. Для всякого u существуют такие x, y, что (x, u, y) P и для всех x, y, если (x, u, y) P, то (x = x y = y) (x = y y = x).

Элементы множества X называются вершинами, элементы U — ребрами, а отношение P — инцидентором графа L.

Высказывание (x, u, y) P читается так: ребро u соединяет вершину x с вершиной y, или, что то же, u соединяет пару (x, y).

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

Легко проверить, что для каждого u U истинно одно и только одно из следующих трёх высказываний:

Существуют такие x, y, что x y, (x, u, y) P, (y, u, x) P;

Существует такой x, что (x, u, x) P;

Существуют такие x, y, что x y, (x, u, y) P, (y, u, x) P.

В соответствии с этим множество U рёбер разбивается на три попарно не пересекающихся подмножества

Ы, Щ, '55.

Элементы множества Ы (для которых истинно первое из трёх высказываний) будем называть дугами, элементы множества Щ (для которых истинно второе высказывание) — петлями, а элементы U (для которых истинно третье высказывание) — звеньями.

Пусть для некоторой тройки элементов (x, u, y) истинно высказывание (x, u, y) P, т.е. ребро u соединяет вершину x с вершиной y; если при этом ещё u Ы, то говорим: дуга u идёт из вершины x в вершину y, — а если u Щ ( и значит y = x), то говорим: u есть петля при вершине x.

Две вершины x и y называются смежными, если существует, по крайней мере, одно соединяющее их ребро, т.е. если истинно высказывание:

существует u такое, что (x, u, y) P или (y, u, x) P.

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

Определим бинарные отношения I+, I-, I0, I :

(x, u) I+ тогда и только тогда, когда существует y такой, что (x, u, y) P;

(x, u) I- тогда и только тогда, когда существует y такой, что (y, u, x) P;

(x, u) I0 тогда и только тогда, когда (x, u, x) P;

(x, u) I тогда и только тогда, когда (x, u) I+ I- I0.

Теперь для произвольных u U и x X мы говорим, что ребро u и вершина x инцидентны или не инцидентны, смотря по тому (x, u) I+ или (x, u) I+.

Например, на рис 1. инцидентны: вершина a и рёбра 1, 2, 3; вершина b и рёбра 2, 4. Вершина b и ребро 3 не инцидентны.

Рис. 1.

Два ребра u и v называются смежными, если для некоторого x выполняется условие (x, u) I и (x, v) I.

Иными словами, два ребра u и v смежны, если и только если существует хотя бы одна инцидентная им вершина; в частности, всякое ребро смежно само с собой.

Например, на рис 1. рёбра 1 и 1, 1 и 2, 1 и 3, 2 и 3, 2 и 4 смежны, а рёбра 3 и 4 — нет.

Граф L = (X, U; P) называется:

- конечным, если конечны множества X, U;

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

Частным случаем вырожденного является пустой (безрберный) граф, т.е. такой у которого U = .

КОНЕЦ