Особенности дискретных автоматов

Теория конечных автоматов характеризуется широким использованием в различных областях применения дискретной техники. Эта теория получила первоначальное развитие на базе

Особенности дискретных автоматов

Контрольная работа

Радиоэлектроника

Другие контрольные работы по предмету

Радиоэлектроника

Сдать работу со 100% гаранией
в дискретную информацию. Отсюда следует универсальность алфавитного способа задания информации.

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

Абстрактным алфавитом называют любую конечную совокупность объектов (букв) данного алфавита. Природа этих объектов в данном случае не существенна. Важно лишь то, чтобы рассматриваемый алфавит был конечным, то есть состоял из конечного числа букв [24–26]. В абстрактном алфавите можно считать целые слова конкретного языка отдельными буквами, если это необходимо при удобстве преобразования информации.

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

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

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

При рассмотрении многофункциональных автоматов Мараховского (многофункциональных автоматов 1-го, 2-го и 3-го рода) с памятью, которые в процессе функционирования под влиянием пустого слова е могут изменять структуру запоминания в схеме памяти, дискретное автоматное время не подходит. В этом случае вводиться непрерывное автоматное время, в котором слову е выделяется длина, как букве абстрактного алфавита [55].

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

Рассмотрим понятие преобразование информации, которая представлена в алфавитной форме. С абстрактной точки зрения преобразование информации есть отображение одного класса явлений в другой класс явлений в соответствии с определенным законом. Например, явление из некоторого класса А явлений влечет за собою некоторое определенное явление из того же самого или из другого класса явлений В, то говорят, что задано преобразование информации

→ = f( )1,(1.1)

где стрелка «→» – знак преобразования информации, то есть отображение явления в явление .

Если подобное отображение осуществляется определенным объектом, то такой объект называется преобразователем информации.

Алфавитным отображением (оператором) называется всякое соответствие (функция), сопоставляющее слово в том или ином алфавите слова в том же самом или в некотором другом фиксированном алфавите.

Первый алфавит при этом называется входным, а второй – выходным алфавитом другого оператора. В случае совпадения входного и выходного алфавита говорят, что алфавитный оператор задан в соответствующем алфавите.

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

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

С каждым алфавитным оператором связывается интуитивное представление о его сложности. Наиболее простыми являются операторы, осуществляющие побуквенное отображение. В автоматах без памяти используется побуквенное отображение, в которых каждая буква х входного слова р заменяется некоторой буквой у выходного оператора q, зависящей только от буквы х, но не от выбора входного слова р. Побуквенное отображение определяется заданием соответствия между буквами входного и выходного алфавита.

Большое значение имеет кодирующее отображение, которое называют просто кодированием. В наиболее простом виде кодирование заключается в сопоставлении каждой букве а1 алфавита А некоторой конечной последовательности в алфавите B, называемой кодом соответствующей буквы. Различным буквам алфавита А сопоставляются различные коды. Кодирующее отображение должно быть обратимым, то есть взаимная однозначность соответствующего кодирующего отображения. Обратимость кодирования будет всегда выполняться, если соблюдаются следующие два условия:

    коды различных букв исходного алфавита А различны;

    код любой буквы алфавита А не может совпадать ни с каким из отрезков кодов других букв алфавита В. С помощью простейших эквивалентных преобразований, информацию, заданную в любом конечном алфавите, можно записать в стандартном двоичном алфавите, содержащим две цифры (буквы) 0 и 1. Двоичное кодирование должно соблюдаться при выполнении следующего соотношения:

2m ≥ n,(1.2)

дискретный автомат кодирование алфавит

где n – число различных букв исходного алфавита А;

m – количество цифр двоичного алфавита, необходимых для кодирования букв алфавита А.

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

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

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

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

2.2 Понятие об алгоритме

Понятие алгоритма является одним из фундаментальных понятий современной математики. Известно, что слово алгоритм пришло из Персии. Предложил его автор книги c математики Abu Jafer Mohammed ibn Musa al Khowarizmi. Он определил его как определенный специальный метод разрешения поставленной проблемы.

Любое целенаправленное действие сложной системы связано с понятием алгоритма. Он определяет последовательность действий объекта для достижения цели. Так первобытные люди придумывали алгоритмы охоты и изобретали алгоритмы первых кулинарных рецептов. Алгоритмы повседневной жизни человека отличаются неоднозначностью и расплывчивостью выбора принятия решений, не всегда оптимальным исполнением. Это соответствует действию системы в ситуации с неполной информацией. Когда, как говорят, «картина» для человека ясна, то он старается действовать наиболее оптимальным или известным ему способом.

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

Потребности человечества в обобщении многочисленных подходов к решению разнообразных задач привели к созданию теории алгоритмов.

Понятие алгоритма является одним из фундаментальных понятий современной математики. В математической теории алгоритмов существует большое разнообразие определений алгоритма, которые ориентированы на различные способы вычислительной реализации. Например, арифметическое исчисление предикатов (К. Гедель, 1931), λ-определимые (А. Черч, 1936) и частично-рекурсивные (С. Клини, 1936) функции, машины Поста и Тьюринга (Э. Пост, 1936 и А. Тьюринг, 1937), алгоритмы Маркова (А. А. Марков, 1951) и многих других видных ученых. Попытку описать общую теорию алгоритмов предпринял В. М. Глушков в книге «Теория алгоритмов» [25], в которой он с системных позиций описал абстрактную теорию алгоритмов и связал ее с компьютерами, автоматами и самосовершенствующимися системами.

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

Похожие работы

< 1 2 3 4 5 > >>