Основы автоматных преобразований - раздел Информатика, ИНФОРМАТИКА Цифровой (Конечный) Автомат – Это Образ Элемента С Конечной Памятью, Который ...
Цифровой (конечный) автомат – это образ элемента с конечной памятью, который реализуется через механизм «смены состояний», каждое из которых отражает некоторую предысторию поступления входных сигналов. В разных состояниях автомат может по-разному реагировать на одинаковые входные воздействия.
Под воздействием входного слова (последовательности символов, возникающей в моменты времени t = 0, 1, 2, ... i ... , которые называются тактами) автомат переходит из одного состояния в другое и выдает выходное слово. Слово на выходе автомата в такте определяется в общем случае входным словом, поступившим в этом такте на вход автомата, и внутренним состоянием автомата, которое явилось результатом воздействия на автомат входных слов в предыдущие такты. Таким образом восприняв сигнал Хt в ответ автомат формирует сигнал Yt с учетом предыстории.
При анализе автомата его заменяют автоматом с одним эквивалентным входом и одним эквивалентным выходом и считают, что эквивалентные входной сигнал Xt и выходной сигнал Yt принимают значения из соответствующих образом преобразованных алфавитов входных и выходных сигналов.
Рассмотрим примеры автоматов.
1.
Yt=1, если Xt=9, а непосредственно перед этим было Xt-1=2, Xt-2=1 и
Xt-3 = 1; в противном случае Yt = 0.
2.
Yt = 1, если Xt = 1 и до такта t число единичных значений Xi было нечетно; в противном случае Yt = 0.
Для автоматов существует формализованная система описания (автоматные преобразования).
Чтобы описать автомат нужно задать закон (функцию) переходов автомата из одного состояния в другое и функцию выходов (реакции на входные воздействия в каждом состоянии).
Опишем рассмотренный ранее автомат А2.
1) X=(0, 1) - входной алфавит.
2) Y=(0, 1) - выходной алфавит.
3) S=(S0, S1) - алфавит состояний. S0 - отражает факт прихода
ранее четного числа X=1. S1 - отражает факт прихода
ранее нечетного числа X=1.
4) S0 - начальное состояние автомата.
5)S(t)= Ф(X(t), S(t-1)) - функция переходов;
Y(t)= F(X(t), S(t-1)) - функция выходов.
Функция переходов и функция выходов однозначно определяют зависимость состояния автомата в такте t и зависимость выходного сигнала Y(t) от входного сигнала в такте t и состояния в такте (t-1).
Пример табличного описания автомата А2:
функции переходов. функции выходов.
Посмотрим, как по такому описанию можно проанализировать поведение автомата А2 в моменты времени t = 0, 1, 2, 3, 4. Пусть задано начальное состояние автомата S0 и значение входных сигналов в указанные моменты времени:
Найдем последовательность Y и S:
Y(t)=F(X(t), S(t-1));
S(t)=Ф(X(t), S(t-1)).
Алгоритм заполнения таблицы:
1. Зная S(t-1) и X(t), определяем Y(t) по функции выходов.
2. Зная S(t-1) и X(t), определяем S(t) по функции переходов.
3. Возвращаемся к пункту 1.
Получим следующую последовательность Y(t) и S(t).
Автомат может быть описан и в виде ориентированного графа. При этом состояния автомата представляются вершинами графа, входы и выходы автомата отмечаются соответственно как числители и знаменатели дробей, расположенных на дугах, направленно соединяющих вершины графа.
Ниже приведено графическое задание автомата А2.
Функциям вида:
Y(t)=F(X(t),S(t-1)),
S(t)=Ф(X(t),S(t-1)), t=1,2, ...
соответствует автомат, выходной сигнал которого зависит от состояния автомата и сигнала на его входе. Такой автомат называется автоматом МИЛИ.
Рассмотрим автомат МИЛИ как устройство, работающее в некоторой системе тактов (часов). Его поведение можно описать следующей блок-схемой:
Выход автомата МИЛИ в такте t зависит от воздействия в такте t:
Y(t)=F(X(t),S(t-1))
В устройствах ЭВМ также широко применяются и так называемые автоматы с задержанной реакцией. У таких автоматов выходной сигнал Y(t) в такте t зависит исключительно от состояния автомата S(t-1) в такте и не зависит от входного сигнала X(t). Наиболее изученные и употребляемые автоматы такого вида это - автоматы МУРА.
Пример графического описания некоторого автомата МУРА:
Выходы "Y" определяется только значением состояний S и соответственно задается не на дугах, а у вершин. Входы, как и в автомате Мили, задаются на дугах.
Функции переходов и выходов для автоматов МУРА также могут задаваться в форме таблиц.
Пусть задано графическое описание автомата Мура:
X =<0;1>
Y = <0;1>
Соответствующее табличное описание имеет вид:
Поведение описанного автомата Мура во времени отражает приведённая ниже таблица.
МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ... ПУТЕЙ СООБЩЕНИЯ МИИТ... Кафедра Вычислительные системы и сети...
Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ:
Основы автоматных преобразований
Что будем делать с полученным материалом:
Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:
Предшественники электронных вычислительных машин
Первое автоматическое устройство для выполнения операции сложения было создано в 1623 году в Германии Вильгельмом Шикардом на базе механических часов.
Поколения электронных вычислительных машин
На протяжении пяти десятилетий электронная вычислительная техника очень быстро развивается, за это время сменилось несколько поколений ЭВМ.
Поколение ЭВМ определяется совокупностью взаимоо
Упрощенная структура компьютера и принцип его работы.
Современные ЭВМ (компьютеры) имеют разнообразную конфигурацию (состав, физическую и логическую организацию). Однако во многих случаях их упрощенная структура может быть отображена рисунком 1.
Программное обеспечение компьютера
Для того, чтобы ЭВМ была ЭВМ, т.е. могла выполнять любые действия по обработке информации, необходимо составить на понятном ей языке последовательность команд, т.е. программу
История языков программирования
Программы для первых компьютеров писали на «машинном» языке, т.е. в кодах, непосредственно воспринимаемых компьютером.
В начале 50-х годов появился язык ассемблер*
Основные характеристики компьютеров
Важнейшими эксплуатационными характеристиками ЭВМ являются ее производительность Р и общий коэффициент эффективности машины Э:
Э = Р/ (Сэвм + Сэк),
Сэвм – стоимос
МикроЭВМ
С появлением в 70х годах прошлого века сверхбольших интегральных схем стало возможным создавать на одной микросхеме упрощенный вариант процессора – микропроцессор с числом разрядов в слове 8-16 и б
Персональные компьютеры
Первые персональные компьютеры появились в середине 70-х годов. Их разработали независимо друг от друга фирмы IBM и Apple. Однако стоимость компьютеров была слишком высока, и поэтом
Большие ЭВМ и СуперЭВМ
Большие ЭВМ (мэйнфреймы) – это мощные компьютеры общего назначения. Их применяют для обслуживания очень крупных организаций и даже целых отраслей народного хозяйства. На базе таких компьютеров созд
Представление чисел в позиционной системе счисления
Под системой счисления понимается способ представления любого числа с помощью некоторого алфавита символов, называемых цифрами. Существуют различные системы счисления. От их особенностей зав
Случай, когда система счисления является целой степенью числа 2
Рассмотрим правила преобразования восьмеричных и шестнадцатеричных чисел в двоичные и наоборот. Эти правила исключительно просты, т.к. основания восьмеричной и шестнадцатеричной систем есть целые с
Общий случай перевода
Общие правила перевода чисел из десятичной системы счисления в другую приведены ниже
1) Для целых чисел.
Делим число на основание той системы счисления, в которую переводим данное
Двоичная арифметика
Правила выполнения арифметических действий над двоичными числами задаются таблицами двоичных сложения, вычитания и умножения.
Таблица Таблица Таблица
двоичного двоичного двоичного
Представление чисел в форме с фиксированной и плавающей точкой
В ЭВМ применяют две формы представления чисел: с фиксированной точкой (естественная форма) и плавающей точкой.
При представлении чисел с фиксированной точкой положение точки фиксируется в
Коды для представления чисел в компьютере
Взаимно однозначное преобразование слов называется кодированием. В ЭВМ в целях упрощения выполнения арифметических операций применяют специальные коды для представления чисел. При п
Прямой код
Прямой код двоичного числа G, представляемого в n - разрядной сетке, определяется как
G , при G>=0;
G
Обратный код
Обратный код двоичного числа G, представляемого в n - разрядной сетке, определяется как
G , при G>=0;
Дополнительный код
Дополнительный код двоичного числа G, представляемого в n - разрядной сетке, определяется как
G ,
Смещенный код.
Помимо рассмотренных кодов для представления чисел со знаком применяется еще смещенный код. Этот код обычно используется для представления целых чисел, задающих порядки чисел с плавающей точкой. Оп
Сложение чисел в форме с плавающей точкой
Сложение двух чисел, представленных в форме с плавающей точкой осуществляется по следующему алгоритму:
Определение разности R (с помощью алгебраического сложения) порядков заданных чисел с
Кодирование текстовой информации
Современные ЭВМ обрабатывают не только числовую, но и текстовую, другими словами – алфавитно-цифровую информацию, содержащую цифры, буквы, знаки препинания, математические и другие символы. Такой х
Кодирование графической информации
Если рассмотреть с помощью увеличительного стекла черно-белое графическое изображение, напечатанное в газете или книге, то можно увидеть, что оно состоит из мельчайших точек, образу
Кодирование звуковой информации
В отличие от текстовых, числовых и графических данных, у звукозаписей не было столь длительной истории кодирования. Методы кодирования звуковой информации двоичным кодом далеки от с
Представление команд
В общем случае команда состоит из операционной части и адресной части.
Каждая ЭВМ имеет свой набор команд. Полный набор к
Основные структуры данных
Автоматизированная обработка больших объемов данных происходит проще, когда данные упорядочены, т.е. образуют заданную структуру. Среди существующих типов структур данных можно выделить три основны
Режимы и технологии работы с базами данных
Система управления базами данных имеет два режима работы: проектировочный и пользовательский. Первый режим предназначен для создания или изменения структуры базы данных и создания инструментов для
Получение информации из Интернета
Интернет – всемирная компьютерная сеть. Если два компьютера, находящиеся на разных континентах, обмениваются данными в Интернете, это совсем не значит, что между ними действует одно
Структура документа на языке HTML
1) Документ HTML всегда должен начинаться с тега <HTML> и заканчиваться соответствующим закрывающимся тегом </HTML>.
2) Внутри документа выделяются два основных раздела: раздел
Функциональные блочные элементы
Основными функциональными элементами являются заголовки и абзацы. Язык HTML поддерживает шесть уровней заголовков. Они задаются при помощи парных тегов <H1> до <H6>. Эти элементы отобра
Web-графика
Графические элементы Web-страниц используют два основных формата – GIF и JPEG (допустим формат PNG).
Файлы формата GIF (Graphic Interchange Format) – файл упакован и занимает меньше места,
Средства антивирусной защиты
Основным средством защиты информации является резервное копирование наиболее ценных данных. В случае утраты информации по какой-либо причине жёсткие диски переформатируют и подготавливают к новой э
Понятие несимметричного шифрования информации
Обычный подход состоит в том, что к документу применяется некий метод шифрования (назовём его ключом), после чего документ становится недоступен для чтения обычными средствами. Его может про
Принцип достаточности защиты
Защита публичным ключом (впрочем, как и большинство других видов защиты информации) не является абсолютно надёжной. Поскольку каждый желающий может получить и использовать чей-то публичный ключ, то
Понятие электронной подписи
Итак, клиент может переслать организации свои конфиденциальные данные (например, номер электронного счёта). Точно так же он может общаться и с банком, отдавая ему распоряжения о пер
Понятие электронных сертификатов
Системой несимметричного шифрования обеспечивается делопроизводство в Интернете. Благодаря ей каждый из участников обмена может быть уверен, что полученное сообщение отправлено именно тем, кем оно
Математические основы синтеза схем
Физическим аналогом букв двоичного алфавита (0 и 1) в схемах ЭВМ являются низкий и высокий потенциал, отсутствие и наличие импульса и т.п. Работу любой схемы ЭВМ можно представить следующим образом
Основы булевой алгебры. Булевы функции
Переменные, принимающие два значения: 0 и 1 (ложь и истина), называются булевыми (двоичными, логическими).
Основными операциями булевой алгебры является инверсия, конъюнкция и дизъюнкция.
Законы булевой алгебры.
Законы булевой алгебры можно выразить в виде формул:
Удобно выделить законы, облегчающие преобразования формул к более пр
Хотите получать на электронную почту самые свежие новости?
Подпишитесь на Нашу рассылку
Наша политика приватности обеспечивает 100% безопасность и анонимность Ваших E-Mail
Y(t)=F(X(t), S(t-1));
Выход автомата МИЛИ в такте t зависит от воздействия в такте t:
Новости и инфо для студентов