Виталий Сигорский - Математический аппарат инженера

Тут можно читать онлайн Виталий Сигорский - Математический аппарат инженера - бесплатно полную версию книги (целиком) без сокращений. Жанр: Математика, издательство Технiка, год 1977. Здесь Вы можете читать полную версию (весь текст) онлайн без регистрации и SMS на сайте лучшей интернет библиотеки ЛибКинг или прочесть краткое содержание (суть), предисловие и аннотацию. Так же сможете купить и скачать торрент в электронном формате fb2, найти и слушать аудиокнигу на русском языке или узнать сколько частей в серии и всего страниц в публикации. Читателям доступно смотреть обложку, картинки, описание и отзывы (комментарии) о произведении.

Виталий Сигорский - Математический аппарат инженера краткое содержание

Математический аппарат инженера - описание и краткое содержание, автор Виталий Сигорский, читайте бесплатно онлайн на сайте электронной библиотеки LibKing.Ru
Излагаются практически важные разделы аппарата современной математики, которые используются в инженерном деле: множества, матрицы, графы, логика, вероятности. Теоретический материал иллюстрируется примерами из различных отраслей техники. Предназначена для инженерно-технических работников и может быть полезна студентам ВУЗов соответствующих специальностей.

Математический аппарат инженера - читать онлайн бесплатно полную версию (весь текст целиком)

Математический аппарат инженера - читать книгу онлайн бесплатно, автор Виталий Сигорский
Тёмная тема
Сбросить

Интервал:

Закладка:

Сделать

При реализации автоматов в двоичном структурном алфавите можно использовать рассмотренные ранее методы синтеза

- 571 -

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

Заменяя десятичные числа их двоичными эквивалентами читаемыми сверху вниз - фото 112

Заменяя десятичные числа их двоичными эквивалентами, читаемыми сверху вниз, получаем таблицу соответствия, в которой значения функций s( ν + 1) и у ( ν ) представлены двоичными кодами:

Рис 239 Структурная схема конечного автомата Отсюда видно что комбинационная - фото 113 Рис 239 Структурная схема конечного автомата Отсюда видно что комбинационная - фото 114

Рис. 239. Структурная схема конечного автомата

Отсюда видно, что комбинационная схема должна иметь четыре входа, соответствующие входным переменным x 1 ( ν ), х 2 ( ν ) и переменным состояния s( ν ), s 2( ν ) , а также три выхода, соответствующие переменным состояния s 1 ( ν + 1), s 2( ν + 1) и выходной переменной у 1 ( ν ). Синтезировав комбинационную схему, соответствующую полученной таблице и введя два элемента задержки З 1и З 2, получим структурную схему автомата (рис. 239).

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

- 572 -

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

Рис 240 Граф конечного автомата а и его сокращенная форма б - фото 115

Рис. 240. Граф конечного автомата ( а ) и его сокращенная форма ( б )

Минимизация числа состоянии полных автоматов связана с отношением эквивалентности. Пусть автоматы М 1 и М 2 , находящиеся соответственно в начальных состояниях, σ iи σ j(обозначения М 1 и М 2 могут относиться к одному и тому же автомату), под воздействием любой входной последовательности выдают одинаковые выходные последовательности, т. е. автоматы М 1 и М 2 в данных состояниях σ iи σ jнеразличимы по внешним выходам. Такое отношение между состояниями одного и того же или двух различных автоматов обладает свойствами рефлексивности, симметричности и транзитивности, следовательно, оно является отношением эквивалентности состояний. Если состояния не эквивалентны, то их называют различимыми. Легко доказать справедливость следующих положений:

1) состояния σ iи σ jавтомата явно различимы, если различаются соответствующие, им строки в таблице выходов;

2) состояния σ iи σ jавтомата явно эквививалентны, если соответствующие им строки в таблице переходов и таблице выходов одинаковы или становятся одинаковыми при замене каждого номера σ iна номер σ j(или наоборот).

Например, для автомата, граф которого изображен на рис. 240, а , общая таблица переходов имеет вид:

- 573 -

Из этой таблицы следует что состояния из множества 0 3 4являются явно - фото 116

Из этой таблицы следует, что состояния из множества {0, 3, 4}являются явно различимыми с любым состоянием из множества {1, 2, 5, 6}. Поэтому следует искать эквивалентные состояния только среди элементов, принадлежащих одному из этих множеств. Так как строки 0 и 4 одинаковы, а строки 1 и 5 становятся одинаковыми при замене цифры в числителе 1 на 5 (или 5 на 1), то явно эквивалентными являются пары состояний {0,4} И {1,5}.

Объединяя эквивалентные состояния в автомате М 1 , получаем эквивалентный автомат М 2 с меньшим числом состоянии, который в любом состоянии нельзя отличить от исходного, наблюдая сигналы на выходах. Очевидно, автоматы М 1 и М 2 являются эквивалентными, если каждому состоянию σ i, автомата М 1 соответствует, по крайней мере, одно эквивалентное ему состояние автомата M 2 , и если каждому состоянию σ j, автомата М 2 соответствует хотя бы одно эквивалентное ему состояние автомата М 1.

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

574 Первая таблица соответствует объединению пар эквивалентных состоянии - фото 117 574 Первая таблица соответствует объединению пар эквивалентных состоянии - фото 118

- 574 -

Первая таблица соответствует объединению пар эквивалентных состоянии {0,4} и {1, 5}, а вторая - объединению пары {2, 6}. Сокращенный автомат содержит только четыре состояния (рис.240, б).

8. Эквивалентное разбиение. Если известны все пары эквивалентных состояний конечного автомата, то тем самым на множестве S его состояний определено отношение эквивалентности, которому соответствует некоторое разбиение на классы эквивалентности S = {S 1, S 2..., S ν } . При этом состояние, не имеющее эквивалентного ему состояния, составляет класс эквивалентности, единственным элементом которого является это состояние. Обозначим через σ ' 0, σ ' 1, ..., σ ' νпредставители классов эквивалентности и через М' – автомат, множеством состояний которого является семейство представителей S '= {σ ' 0, σ ' 1, ..., σ ' ν}. Можно утверждать, что автоматы М и М' эквивалентны ( М ~ М' ), причем М' имеет минимальное число состояний, т. е. является минцмальной формой автомата.

Читать дальше
Тёмная тема
Сбросить

Интервал:

Закладка:

Сделать


Виталий Сигорский читать все книги автора по порядку

Виталий Сигорский - все книги автора в одном месте читать по порядку полные версии на сайте онлайн библиотеки LibKing.




Математический аппарат инженера отзывы


Отзывы читателей о книге Математический аппарат инженера, автор: Виталий Сигорский. Читайте комментарии и мнения людей о произведении.


Понравилась книга? Поделитесь впечатлениями - оставьте Ваш отзыв или расскажите друзьям

Напишите свой комментарий
x