Логические средства и аксиоматические описания.

Под логическими средствами подразумеваются прежде всего способы точного формулирования утверждений и проведения правильных рассуждений, успешно применяемые в математической и научной практике. Утверждения записываются в логике в виде логических формул. В языках программирования логические формы называют логическими выражениями, в отличие от арифметических выражений они принимают только два истинностных значения, 0 или 1, true или false. Из первичных или атомных формул с помощью логических связок и кванторов строятся более сложные формулы. Важно, чтобы синтаксис логических выражений позволял однозначно восстанавливать смысл записываемых утверждений и был по возможности прост и удобен для восприятия и применения.

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

Самая известная среди них программная логика Хоара, формулы которой имеют вид P{S}Q, где Р и Q формулы логики, a S - оператор. Семантика такой формулы определяется следующим образом. Пусть заданы оператор S и интерпретация формул Р и Q. Тогда формула P{S}Q истинна, если для любого состояния σ, в котором формула Р истинна и результат σ‘ оператора S определен, формула Q истинна в состоянии σ’. Формулу Р называют предусловием, а σ- постусловием для оператора S.

Графовые средства: графы, сети, диаграммы.

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

Граф G={V,R} можно рассматривать, как двухместное бинарное отношение R на множестве V, которое определяется, как множество упорядоченных пар элементов множества V.

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

Конечно-автоматные диаграммы.

Существуют разные варианты этого понятия. Один из них определяется следующим образом. Задается конечный помеченный мультиграф, один узел которого помечен как начальный и один или несколько узлов помечены как конечные, или заключительные. Имеется входной алфавит ∑ ⁼ {a₁,...,a_k}, и каждая дуга помечена символом этого алфавита. Надстройка заключается в том, что с диаграммой D связывается определяемый ею язык L(D), состоящий из слов, соответствующих путям из начального узла в конечные. Словом, соответствующим пути rl, r2,..., rl, называется такое слово xl, х2... х1, в котором xi — символ, помечающий дугу ri (i = 1,…,1)

Мы дали статическое описание языка L(D), но его можно описать более динамически или операционно. При этом множество узлов диаграммы трактуется как множество состояний Q = {ql,..., qn}, а перемещение из узла qi в узел qj по дуге, помеченной а, как переход из состояния qi в состояние qj под действием входного символа а. Тогда путь в диаграмме можно рассматривать как вычисление для входного слова, соответствующего этому пути. Если для любого aє∑ из каждого узла выходит не более одной дуги, помеченной сим­волом aє∑, то диаграмма задает детерминированный конечный автомат, который начинает работу в начальном состоянии и, читая в текущем состоянии q текущий входной символ а, переходит в то состояние q', куда ведет дуга, помеченная а. Если, прочитав входное слово φ, автомат попадает в заключительное состояние, то φєL(D) (говорят, что автомат допускает или распознает такое φ). Недетерминированная диаграмма задает для слова φ некоторое множество вычислений пли путей переходов, и если в нем есть вычисление, заканчивающееся в заключительном состоянии, то φєL(D).

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

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

Синтаксические диаграммы.

Для описания синтаксиса языков программирования используются в основном два средства: БНФ (Бэкуса - Наура формы) и синтаксические диаграммы. Исторически первыми были БНФ. При разработке языка Алгол-60 рабочей группой Международной федерации по обработке информации (IFIP -International Federation on Information Processing) была придумана нотация в виде металингвистических формул для описания правил грамматики языка. Такие формулы позволяют во многих случаях компактно описывать языки. Например, условный оператор можно описать в виде:

(условный оператор)::= IF< условие) THEN < оператор) | ELSE (оператор)

В БНФ знак «::=» читается «это есть» и разделяет левую и правую часть правил. Знак «I» (вертикальная черта) читается «или» и разделяет возможные альтернативы в правой части правила. Угловые скобки выделяют текст -название понятия языка (нетерминального символа). Это минимальные средства БНФ. Эти символы используются в правых частях правил и позволяют несколько упростить набор правил или избежать рекурсии.

Сети Петри.

Сеть Петри - это совокупность С=(Р, Т, I, О), где

Р - множество позиций;

Т - множество переходов;

I - входная функция;

О - выходная функция. Разные варианты сетей Петри используются для асинхронных и параллельных систем.

11. Графические методы спецификации.

 

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

Необходимо отличать графовые средства (связанные с графами) от графических (связанных с графиком), считая, что первые относятся к понятиям, а вторые к способам их изображения в виде рисунков. Граф G={V,R} можно рассматривать, как двухместное бинарное отношение R на множестве V, которое определяется, как множество упорядоченных пар элементов множества V. Говоря о бинарных отношениях, как о графах,

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

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

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

12.Автоматное преобразование информации

Алгоритм является фундаментальной концепцией информатики, и вопрос построения автоматических устройств, реализующих алгоритмы, является одним из главных вопросов вычислительной техники. Хотя теория автоматов изучает достаточно простые модели, она является фундаментом большого числа разнообразных приложений. Эти приложения - от языковых процессоров до систем управления реального времени и протоколов связи микропроцессорных систем - покрывают значительную долю проблем, анализом и реализацией которых занимается информатика. В этом отношении можно привести слова Дуга Росса из компании Soft Tech, утверждавшего, что 80 или даже 90% информатики будет в будущем основываться на теории конечных автоматов. Результат преобразования информации вход —> выход зачастую зависит не только от того, какая информация появилась на входе, но и от того, что происходило раньше. Множество примеров этому дают биологические системы. Таким образом, существуют более сложные устройства, чем функциональные преобразователи информации (комбинационные автоматы); их реакция зависит не только от вектора входных сигналов в данный момент, но и от того, что было на входе раньше, от входной истории. Такие преобразователи называются автоматами с памятью или конечными автоматами. На один и тот же входной сигнал конечный автомат (КА) может реагировать по-разному, в зависимости от того, в каком состоянии он находится в данный момент. При получении входного сигнала КА не только выдает информацию на выход как функцию этого входного сигнала и текущего состояния, но и меняет свое состояние, поскольку входной сигнал изменяет его предысторию. Число входных историй счётно, но бесконечно. Если автомат будет вести себя по разному для каждой возможной предыстории, то он должен иметь бесконечный ресурс (память), чтобы все эти предыстории как-то запоминать. Если ввести на множестве предыстории отношение эквивалентности, то две предыстории можно считать эквивалентными, если они одинаковым образом влияют на дальнейшее поведение автомата. Очевидно, что для своего функционирования автомату достаточно запоминать класс эквивалентности, к которому принадлежит предыстория. Случай, когда количество таких классов эквивалентности конечно, является простейшим. Но именно такая математическая модель представляет значительный интерес и имеет большую практическую ценность. Соответствующая формальная модель называется конечным автоматом. В этой модели внутреннее состояние автомата представляет собой класс эквивалентности предыстории. Упрощенно можно считать, что внутреннее состояние автомата - это его характеристика, однозначно определяющая все последующие реакции автомата на внешние события. Однако, образно говоря, внутреннее состояние автомата - это всё то, что автомат знает о своем прошлом с точки зрения будущего поведения - его реакция на последующие входные сигналы. Можно сказать, что это его предыстория в концентрированном виде (класс эквивалентности предысторий) и реакция автомата на последующие сигналы определяется только текущим состоянием, но не тем, как автомат пришел в него. Конечный автомат - это устройство, работающее в дискретные моменты времени (такты). В каждом такте на вход КА подаются входные сигналы, а на выходе появляется выходной сигнал, зависящий от текущего состояния и поступившего входного сигнала. Моменты срабатывания (такты) определяются либо тактирующими синхросигналами, либо асинхронно, наступлением внешнего события, которое заключается в приходе сигнала. В этом случае говорят об управлении автомата событиями, и такты работы КА имеют различную длительность.

 

13. Основные понятия и определения теории конечных автоматов