Минимизация абстрактных автоматов.

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

метод№1: метод таблиц эквивалентных состояний.

А
(0,1)	(5,6)
(5,6)		(0,1)

1.строется таблица эквив-сти сост-й(А), первыми запис-ся два начал-х сост-я, кот-е подверг-ся анализу.

2.выбирается строка в дан.таблице, ячейки кот-й еще не заполнены и проверяется подобны ли состояния, кот-ми она помечена. Если сост-я не подобны, то два исходных сост-я не эквив-ны и процесс завершен, если подобны, то вычисляется рез-т применения каж-го вход-го сим-ла к этой паре сост-й и записыв-сяполученные пары сост-й.

3. если пара разл-х сост-й(получ-х на 2 шаге) еще не использ-сь как метка, то она перепис-ся на новую строку.

4. если таблица завершена выписыв-ся все состояния, поражденные в ходе проверки,кот.б/т экв-ми сост-ми. В нашем пр-ре 0~1 и 5~6.

Метод поиска экв-х сост-й №1 (метод таблиц экв-х сост-й) не всегда применим,т.к.расс-ся т/о пары экв-х сост-й и каж-й раз для новой пары сос-й н/о строить свою таблицу.

Метод №2: метод разбиения на непересекающиеся подмн-ва.

1.все мн-во сос-й разбив-ся на 2 блока, 1н блок содержит т/о отверг-е, др-й т/о доп-щие сост-ия. Ни олно сост-е 1-го блока не м.б.экв-но как.либо состоянию из 2-го блока.

Р₁=({0,1,2,3},{4,5,6})

2.расс-м переходы в 1м блоке под возд-ем 0. из сост-й 0и1 переход в 5и6- доп-щие сост-ия, из 2и3 переход в 0и3-отверг-е сост-я, значит Р₂=({0,1},{2,3},{4},{5,6}).

3.расс-е поведение блока {2,3} если на входе дей-т серия сим-в 0: они не экв-ны, Р₃=({0,1},{2},{3},{4},{5,6}).

4.дальнейшие попытки разбить блок ={0,1}и {5,6}ничего не дают, значит 0~1 и 5~6.

 

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

1. начать список с начал-го состояния.

2. для каж-го сост-ия, уже внесенного в список, добавить все еще не занесенные в него сос-ия, кот-е м.б.достигнуты под Дей-ем как.либо из входных сим-в.

3. если эта процедура перестает пораждать нов-е состояния, то алг-м завершен и все сост-ия, кот.не проявились по ходу алг-ма не достижимы, соответ-щие строки удаляются.

1

Недостиж-е сост-ия: 1,5

 

Арифметико-логические устройства (АЛУ). Классификация АЛУ.

Арифме́тико-логи́ческое устро́йство (АЛУ) — блок процессора, который под управлением устройства управления (УУ) служит для выполнения арифметических и логических преобразований (начиная от элементарных) над данными, представляемыми в виде машинных слов, называемыми в этом случае операндами.

Операции в АЛУ

Все выполняемые в АЛУ операции являются логическими операциями (функциями), которые можно разделить на следующие группы:

операции двоичной арифметики для чисел с фиксированной точкой;

операции двоичной (или шестнадцатеричной) арифметики для чисел с плавающей точкой;

операции десятичной арифметики;

операции индексной арифметики (при модификации адресов команд);

операции специальной арифметики;

операции над логическими кодами (логические операции);

операции над алфавитно-цифровыми полями.

 

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

 

К арифметическим операциям относятся сложение, вычитание, вычитание модулей («короткие операции») и умножение и деление («длинные операции»). Группу логических операций составляют операции дизъюнкция (логическое ИЛИ) и конъюнкция (логическое И) над многоразрядными двоичными словами, сравнение кодов на равенство. Специальные арифметические операции включают в себя нормализацию, арифметический сдвиг (сдвигаются только цифровые разряды, знаковый разряд остаётся на месте), логический сдвиг (знаковый разряд сдвигается вместе с цифровыми разрядами). Обширна группа операций редактирования алфавитно-цифровой информации. Каждая операция в АЛУ является логической функцией или последовательностью логических функций описываемых двоичной логикой для двоичных ЭВМ, троичной логикой для троичных ЭВМ, четверичной логикой для четверичных ЭВМ, …, десятичной логикой для десятичных ЭВМ и т. д.

Классификация АЛУ:

По способу действия над операндами АЛУ делятся на

последовательные и параллельные. В последовательных АЛУ операнды представляются в последовательном коде, а операции производятся последовательно во времени над их отдельными разрядами. В параллельных АЛУ операнды представляются параллельным кодом и операции совершаются параллельно во времени над всеми разрядами операндов.

По способу представления чисел различают АЛУ:

- для чисел с фиксированной точкой;

- для чисел с плавающей точкой;

- для десятичных чисел.

По характеру использования элементов и узлов АЛУ делятся на

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

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

Генерируемая управляющим блоком последовательность сигналов определяется кодом операции команды и оповещающими сигналами.