Конечные автоматы и формальные грамматики

Техническое воплощение логических операций получило название комбинационных или переключательных схем. Как отмечалось выше логические состояния «1» и «0» задаются в компьютерах и системах связи в виде наличия или отсутствия тока в электронных цепях. Переключательную схему можно получить путем последовательного соединения элементарных электрических цепей с контактами (электрическими выключателями), которые могут замыкать или размыкать электрическую цепь. Возможно следующее представление элементарных логических операций с помощью цепей и контактов (Рис 2.1).

 

Рис 2.1. Представление элементарных логических операций с помощью электрических цепей с контактами

 

Более сложные переключательные схемы, реализующие более сложные логические выражения, можно технически получать путем последовательного присоединения выходов одних электрических цепей элементарных логических схем к входам других электрических цепей реализующих другие элементарные логические схемы. Если комбинационная схема имеет конечное множество входных логических состояний x,y,z…и одно единственное выходное состояние q, то описанный процесс последовательного подсоединения элементарных логических схем соответствует процессу построения логической формулы f(x,y,z…) с помощью операций, реализуемых используемыми электрическими цепями (элементарными логическими схемами). С помощью таких комбинационных логических схем и соответствующим им электрическим цепям технически реализуются устройства хранения, перемещения и осуществления не только логических операций над символами, но и арифметических операций над цифрами. Они образуют, так называемые, триггеры, регистры, сумматоры. Эти технические конструкции образуют те самые специальные устройства, из которых и состоит компьютер. Так устройства для хранения данных состоят из регистров и называются памятью. Устройства для осуществления логических и арифметических операций над данными, состоящие из регистров и сумматоров называются арифметически–логическими устройствами (АЛУ). Особая разновидность этих устройств называется устройствами управления (УУ), ибо логические операции, осуществляемые ими, направлены на управление потоками данных компьютере.

Важной особенностью подобных устройств является то, что их внутренние логические состояния (логические переменные) изменяются с течением времени под воздействием входных воздействий (тоже логических состояний), физически представляемых в виде наличия или отсутствия тока в цепи. Эти входные воздействия иногда называют входными сигналами (x,y,z…..). Напомним, что эти устройства имеют и выходное логическое состояние, которое называется выходным сигналом (q).

Для математического описания подобных устройств вводятся специальные обозначения. Множество входных сигналов обозначается как U , через Q - множество выходных сигналов, а через X - множество внутренних состояний. Для описания изменений во времени удобно ввести понятие дискретного времени. На оси времени отмечаются моменты, в которые входной сигнал может претерпевать изменения. Эти отдельные моменты времени удобно представлять в виде последовательности неотрицательных целых чисел n=0,1,2…. В информатике такие последовательности называют тактами. Уравнение, описывающее работу комбинационной схемы во времени можно записать в виде Q(n)=f(X(n)). Математическое описание комбинационных схем с учетом их внутренних состояний и эволюции этих состояний во времени под воздействием входных сигналов называется конечным автоматом и задается совокупностью пяти величин A=(U,Q,X,f,φ). Здесь f:X∙U→X –функция переходов, φ:X∙U→Q - функция выходов. Функции переходов и выходов обычно задаются соответствующими таблицами или с помощью специальных графиков - направленных графов. Вершины графов изображаемые в виде кружочков, определяют состояния автомата, дуги указывают переходы автомата из одного состояния в другое под воздействием входного сигнала. В скобках указывается выходной сигнал.

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

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

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

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

В заключении еще раз перечислим основные операции математической логики и двоичной арифметики :

 

· Это логические операции: логическое сложение (дизъюнкция, логическое «ИЛИ»), логическое умножение (конъюнкция, логическое «И»), логическое отрицание (инверсия, логическое «НЕ»), логическое следование (импликация), логическая эквивалентность.

· Это арифметические операции: двоичное сложение, двоичное умножение.

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