Описания конечных автоматов и формальных грамматик

Техническое воплощение логических операций получило название комбинационных или переключательных схем. Как отмечалось выше логические состояния «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).

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

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

· Поразрядные логические операции.

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

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

Системы счисления

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

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

Ряд явлений окружающего нас мира, которые носят количественный характер, потребовал введения специального языка для описания понятия числа. Язык чисел, как и обычный язык, имеет свой алфавит, состоящий из специальных знаков получивших название цифр. Алфавит может содержать любое заранее определенное число цифр. Так язык чисел, которым сейчас пользуются практически на всем земном шаре (за исключением арабских стран), имеет алфавит, в котором десять цифр, от 0 до 9. Этот язык (форма представления чисел) называется десятичной системой счисления.

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

Все системы счисления делятся на две группы: непозиционные и позиционные.

В непозиционных системах вес цифры (т.е. тот вклад, который она вносит в значение числа) не зависит от ее позиции в записи числа. Из-за отсутствия зависимости веса цифры от ее позиции, непозиционная система не находит применения в машинных расчетах.

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

Так, в развернутой форме запись числа 888,8 в десятичной системе будет выглядеть следующим образом 888,8₁₀=8·10²+8·10¹+8·10⁰+8·10^-1 .

Как видно из примера, число в позиционных системах счисления записывается в виде суммы числового ряда степеней основания (в данном случае 10), в качестве коэффициентов которых выступают цифры данного числа.

В общем случае в системе счисления с основанием p запись числа А_p производится следующим образом:

A_p=a_n·pⁿ+…+a₀·p⁰+a_-1·p^-1+…+a_-m·p^-m,

где n+1 – число целых разрядов, m – число дробных разрядов, коэффициенты a_i являются цифрами, принадлежащими алфавиту системы счисления с основанием p.

Теоретически за основание системы можно принять любое натуральное число – два, три, четыре и т.д. Практически, наряду с десятичной используются системы с основанием, являющимся целой степенью числа 2 (Табл. 2.13)

Таблица 2.13

Алфавиты различных систем счисления

Система счисления	Основание	Алфавит цифр
Десятичная		0 1 2 3 4 5 6 7 8 9
Двоичная		0 1
Восьмеричная		0 1 2 3 4 5 6 7
Шестнадцатеричная		0 1 2 3 4 5 6 7 8 9 A B C D E F

Запись числа в какой-либо системе исчисления с основанием p означает сокращенную запись выражения.

a_n-1·p^n-1+a_n-2·p^n-2+…+a₁·p¹+a₀·p⁰+a_-1·p^-1+…+a_-m·p^-m (1)

где a_i – цифра системы счисления; n и m – число целых и дробных разрядов соответственно.

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

Полная запись в виде выражения (1) позволяет перевести число в любой системе счисления в десятичное, например,

273₈=2·8²+7·8¹+3·8⁰ =187₁₀