Теория автоматов. Лекция 1 Основные понятия теории конечных автоматов. Элементы логикоматематического языка. 59
 Скачать 1.63 Mb.
|
|
Содержание:
Введение Математический аппарат для построения компьютерных сетей возникла необходимость создания данного учебного пособия для усвоения и систематизации знаний студентов специальности 09.02.02. Компьютерные сети. Необходимость этого учебного пособия оправдана тем, что нет возможности студентам обратиться к большому многообразию литературы в этой области науки. В связи с этим очень удобно, когда весь лекционный материал для написания контрольных работ и выполнению отчетов по практическим работам размещается концентрированно в одном месте. В пособии приводятся основные понятия теории алгоритмов, раскрывается связь между алгоритмами и вычислительными машинами и различия между процессами, протекающими в машинах Тьюринга и автоматах Неймана. Рассматриваются также основы теории конечных автоматов, формальные методы проектирования автоматов на основе абстрактного и структурного синтеза, явление состязаний элементов памяти и гонок в структурном автомате, методы кодирования состояний автоматов и синхронизация автоматов. Приводятся примеры в асинхронном и синхронизируемом исполнении. В данном учебном пособии собраны самые базовые и важные вопросы, которые в обязательном порядке должны знать студенты специальности 09.02.02. Компьютерные сети согласно образовательным стандартам. Теория автоматов - раздел дискретной математики, точнее, теории управляющих систем, в котором рассматриваются и изучаются математические модели преобразователей дискретной информации. Такие модели называют также дискретными моделями. В качестве преобразователей дискретной информации наряду с реальными устройствами (такими, как: вычислительные машины, различные устройства логического управления, различные автоматы по размену денег, продаже газет, воды и штучных товаров, автоматы по обработке деталей и сборке из них крупных узлов и т.п., а также и живые организмы) являются и абстрактные системы (такие, как: математические машины, аксиоматические теории и т.п.). Будем эти преобразователи дискретной информации называть дискретными автоматами. В связи с тем, что алфавит представления информации связан с цифрами некоторой системы счисления, то эти автоматы также называют цифровыми автоматами. В кибернетике автоматами обычно называют различные устройства, предназначенные для переработки информации. Содержательно конечный автомат можно представить как устройство, имеющее входной и выходной каналы и находящееся в дискретные моменты времени (называемые тактовыми моментами) в одном из возможных состояний (положений), которые называют устойчивыми внутренними состояниями автомата. По входному каналу в устройство поступает информация, т.е. в каждый тактовый момент поступают сигналы, соответствующие буквам входного алфавита. По выходному каналу устройство выдает обработанную информацию, т.е. в те же моменты выдает сигналы, соответствующие буквам выходного алфавита. Выходной канал может также служить для связи с другими такими же устройствами. Входной и выходной каналы математически описываются с помощью входных и выходных переменных. Для внутренних состояний автомата вводится так называемая внутренняя переменная, принимающая значение из множества устойчивых внутренних состояний. Итак, в каждый тактовый момент времени автомат, находящийся в каком-то внутреннем состоянии, в результате действия входного сигнала по определенным правилам вырабатывает выходной сигнал и переходит в следующее устойчивое внутреннее состояние, которое может оставаться прежним. Таким образом, с автоматом связаны три множества (алфавиты входов, выходов и внутренних состояний) и две функции - выходов и переходов в следующее внутреннее состояние. Характерной особенностью этих устройств - преобразователей дискретной информации является их дискретность функционирования (в моменты дискретного времени; способность находиться в одном из конечного множества внутренних состояний и скачкообразно переходить из одного состояния в следующее). Множества значений входных и выходных переменных и внутренних состояний, используемых для описания функционирования автоматов, конечны; поэтому их называют также конечными автоматами. Теория автоматов возникла в 50-х годах нашего века в связи с изучением свойств конечных автоматов. Таким образом, термин автомат употребляется в основном в 2-х смыслах: как автоматическое устройство, выполняющее все действия без участия человека, и как математическая модель, описывающая функционирование реальных технических приборов - дискретных автоматов. Имеются различные подходы к определению понятия конечного автомата. При макроподходе, когда интересуются только внешним поведением устройства, т.е. как оно осуществляет переработку входной информации в выходную и в последовательность внутренних состояний, конечный автомат может задаваться или совокупностью функций, или в виде конечного ориентированного графа, или в алгебраической форме и его называют абстрактным конечным автоматом. При микроподходе конечный автомат задается множеством базисных элементов (функциональных элементов - ФЭ) и схемой (правилами) их соединения, т.е. к функционированию добавляется строение автомата. Поэтому в этом случае автоматы называют также структурными автоматами или автоматными сетями. Различные варианты конечных автоматов и близкие им математические модели служат для описания и анализа технических устройств различных систем и процессов, программ и алгоритмов. Важнейшей характеристикой конечного автомата является его поведение. Оно определяется по-разному и в зависимости от него конечные автоматы подразделяются на преобразователи, распознаватели (акцепторы), генераторы и др. Лекция №1 Основные понятия теории конечных автоматов. Элементы логико-математического языка. План лекции:
Математика является не только совокупностью фактов и методов, но и языком для описания фактов и методов различных научных и производственных областей человеческой деятельности. Этот язык является результатом длительного становления (с момента формулировки математических правил на обычном словесном языке), отражает развитие самой математики, и служит “рабочим аппаратом - инструментом” для решения различных задач. В нем можно выделить две составляющие: собственно математический язык - термины и символы, служащие для получения математических моделей (описания объектов и отношений), и логический язык (логические термины и символы), одно из назначений которого заключается в получении из исходных, истинных утверждений новых утверждений, не противоречащих действительности. Это назначение логического языка расширяет возможности самой математики и придает ей некоторый динамизм. К вопросу о эволюции математического языка связь естественного словесного языка и логического языка рассмотрим на следующем примере. Проводя различные рассуждения мы используем союзы и, или (исключающее и неисключающее), частицу не, словосочетания если, то. . . , тогда и только тогда. Если при этом их смысл и назначение сохраняем, используя их символические аналоги &, , и , то, соблюдая при этом определенные правила, приходим к математической логике. И уже Булевы (логические) функции могут выступать в качестве математических моделей для управляющих устройств. В подтверждение этого рассмотрим следующие примеры о лифте, шифраторе и сумматоре. Пример 1.1. Задача о вызове свободного лифта. В подъезде n - этажного дома работают 3 лифта. На каждом этаже имеется устройство, которое при нажатии кнопки позволяет вызывать ближайший свободный лифт. На логическом языке записать условие вызова i - го лифта, i = 1, 2, 3. Рассмотрим решение задачи для случая вызова лифта на 1-ом этаже [1]. Для описания исходного или рабочего (текущего) расположения лифтов введем 3 n переменных x1, y1, z1, x2, y2, z2,..., xn, yn, zn, где xi = 1 в том и только том случае, когда 1-й лифт находится на i -ом этаже и свободен; yi = 1 в том и только том случае, когда 2-й лифт находится на i -ом этаже и свободен; zi = 1 в том и только том случае, когда 3-й лифт находится на i -ом этаже и свободен. Обозначим через f1(x1, y1, z1,..., xn, yn, zn), f2(x1, y1, z1,..., xn, yn, zn), f3(x1, y1, z1, ..., xn, yn, zn) функции, равные 1 в том и только том случае, когда вызывается лифт с номером соответственно 1, 2, 3. Условие вызова 1-го лифта, т.е. характеристика функции f1, есть то, что “1-й лифт свободен и нет свободных лифтов, расположенных на более низком этаже, чем 1-й лифт”.  Аналогично получаем формулы для других функций  (1.1) Эти функции можно получить заданием соответствующих таблиц, но полученные формулы бесповторные, что для аппаратной реализации экономнее по числу логических элементов. Таблица 1.1
Пример 1.2. В качестве примера автомата рассмотрим шифратор (рис.1.1) для кодирования десятичных цифр 4-х значными кодовыми группами, используя 2-ичную систему счисления. Зависимость между значениями входов и выходов шифратора представлена в таблице 1.1. Из таблицы истинности (табл.1.1) получаем канонические уравнения шифратора: y0 = x1 x3 x5 x7 x9 , y1 = x2 x3 x6 x7 , y2 = x4 x5 x6 x7 , y3 = x8 x9 . (1.2) Пример 1.3. Примером дискретного устройства без памяти является двоичный полусумматор, используемый для сложения двух двоичных одноразрядных чисел. Он имеет два входа y и x и два выхода: суммаz1 и значение переноса в следующий разряд z2 . Таким образом, на выходе получаем результат z2 z1. Таблица 1.2.
Выполняем сложение двоичных чисел y и x построчно в таблице 1.2. Для возможного переноса введем вспомогательную величину z2. Таблицу сложения 1.2 можно рассматривать как таблицу истинности булевых функций z2 и z1. Слагаемые относятся к входным столбцам таблицы истинности, в которой два выходных столбца: один для суммы z1, другой для переноса z2. Тогда y + x = z2 z1 , где z1 = y x и z2 = y & x. Полусумматор имеет только 2 входа и 2 выхода и осуществляет сложение только в разряде единиц для многоразрядных слагаемых. Представленные примеры демонстрируют возможности теории булевых функций в области синтеза дискретных устройств для вычислительной и управляющей техники. Пусть C - некоторое конечное множество, его элементы будем называть буквами, а само множество - алфавитом. Каждую конечную упорядоченную последовательность букв из данного алфавита С будем называть словом в алфавите С. Число n символов в последовательности c(1), c(2),..., c(n), образующей слово c = c(1) c(2)... c(n) в алфавите C, называется длиной слова. Через обозначим пустое слово, не содержащее букв, его длина равна 0; множество всех слов в этом алфавите, имеющих длину t, обозначаем Ct. Множество всех слов в алфавите C, длины не большей t, обозначаем C*. Лекция №2 Алгебраическая теория конечных автоматов. Лемма о разрастании. План лекции:
В теории формальных языков большое значение имеют утверждения, в которых формулируется необходимое условие принадлежности языка к тому или иному классу языков. Эти утверждения известны в литературе под названием лемм о разрастании (или лемм о "накачке"). С помощью этих лемм удается доказать, что тот или иной язык не является языком данного класса, например, не является регулярным, контекстно-свободным и т.п. Доказывать подобного рода "отрицательные" утверждения гораздо труднее, чем "положительные" (что язык есть язык данного класса ), ибо в последнем случае требуется придумать любую грамматику соответствующего класса, порождающую данный язык, а в первом нужно каким-то образом доказать, что не существует грамматики этого класса, порождающей язык. Применение лемм о разрастании состоит в следующем: доказав, что предлагаемый язык не удовлетворяет условию леммы о разрастании, мы можем быть уверены в том, что он заведомо не принадлежит соответствующему классу языков, и нам нечего и пытаться искать для него грамматику того же класса. Мы рассмотрим подобного рода утверждения для классов регулярных, контекстно-свободных и линейных языков. Начнем с леммы о разрастании для регулярных языков. Эта лемма утверждает, что любой регулярный язык допускает представление всех своих достаточно длинных цепочек в виде соединения трех цепочек, причем средняя цепочка из этих трех не пуста, ограничена по длине, и ее "накачка" — повторение любое число раз — или выбрасывание не выводит за пределы языка (т.е. дает цепочки, принадлежащие данному регулярному языку). Теорема. Если— регулярный язык, то существует натуральная константа(зависящая от), такая, что для любой цепочки, длина которой не меньше,допускает представление в виде, гдеи, причем для любогоцепочка. Поскольку язык регулярен, то, согласно теореме Клини (см. теорему 7.6), существует конечный автомат  допускающий его, т.е. . Положив , т.е. введя константу как число состояний конечного автомата , фиксируем произвольно цепочку , длина которой не меньше . Так как , то цепочка не является пустой, и мы можем положить  .Поскольку конечный автомат является детерминированным, то существует единственный путь, ведущий из начального состояния в одно из заключительных состояний , на котором читается . Так как длина цепочки не меньше числа состояний , т.е. числа всех вершин графа , то, поскольку число вершин в любом пути ровно на единицу больше числа дуг в этом пути (т.е. длины пути), число вершин в рассмотренном выше пути будет больше, чем число всех вершин графа. Это значит, что хотя бы одна из вершин данного пути повторяется и она, таким образом, в силу следствия 5.1, содержится в некотором контуре. Обозначим эту вершину через . Тогда путь, несущий цепочку , разбивается на три части:
Обозначая через цепочку, читаемую на первой части пути, через — цепочку, читаемую на контуре, а через — цепочку, читаемую на третьей части, получим , причем поскольку любой контур есть простой путь, то (длина простого пути не может быть больше, чем число вершин графа) и , так как контур имеет ненулевую длину. Но теперь совершенно очевидно, что контур (на котором лежит вершина ) можно пройти (по пути из в ) любое число (при ) раз или ни разу. В первом случае на этом пути будет прочитана цепочка при , а во втором — и цепочка . Таким образом, любая цепочка  содержится в языке . | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||