Реализация компактного представления

Файл ttfsm.c содержит пример компактного представления для конечного автомата, принципиальная схема которого приведена на рис. 26.4.

Массив ttstab содержит 22 действительные записи, каждая из которых соответствует одному из переходов, показанных на рис. 26.4 (а также дополнительную запись, отмечающую конец массива). Каждая запись в массиве состоит из структуры fsm_trans, которая определяет один переход. Следует отметить, что массив ttstab является и компактным, и удобным в определении. Он является компактным, поскольку не содержит пустых записей; он является удобным в определении, поскольку каждая запись непосредственно соответствует одному из переходов конечного автомата.

--------33. Анализ конечных автоматов

Анализ конечных автоматов.

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

Полное описание поведения автомата Мили заключается в определении последовательности выходных букв  при возбуждении его в тактовые моменты времени последовательностью входных букв . Очевидно, что в этом случае  L (здесь А*, В*, L – длина слова), а автомат должен быть инициальным (настроенным) при известных характеристических функциях : Q x A0 и :Q x AB

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

а) Типы особых состояний автомата

В автомате a₁ q­₂

q₁ q₂ q₃

q₀-преходящее

q₂ –тупиковое состояние ,то есть

q₃-изолированное

1) переходящее (недостижимое) состояние, из которого можно перейти, по крайней мере, в одно другое состояние, но после этого уже нельзя возвратиться в него ни при каком воздействии (то есть соответствующая вершина графа автомата не имеет заходящих дуг, но имеет хотя бы одну исходящую дугу);

2) тупиковое состояние, в которое можно перейти, по крайней мере, из одного другого состояния, но после этого уже нельзя выйти из него ни при каком воздействии (то есть соответствующая вершина не имеет исходящих дуг в другие вершины, но имеет хотя бы одну входящую дугу из другой вершины);

3) изолированное состояние, из которого нельзя перейти ни в какое другое состояние и в него нельзя попасть ни из какого другого состояния (соответствующая вершина содержит только петлю).

б) Типы подавтоматов автомата.

Аналогичные определения можно дать для некоторых совокупностей состояний, рассматриваемых как подавтоматы.

Если начальное состояние q₀ конечного автомата U₃ принадлежит непустому множеству Q_i (Q_i  Q) состояний, которое составляет тупиковый или изолированный подавтомат, то автомат U₃ можно упростить исключением всех состояний, которые не принадлежат множеству Q_i, и всех дуг, начинающихся в этих состояниях.

Очевидно, что выделение переходящих, тупиковых и изолированных подавтоматов соответствует разбиению множества Q состояний автомата U=<A,Q,B,δ,λ> на непересекающиеся подмножества Q_n, Q_T, Q_u, представляющие собой классы эквивалентности, т.е.

Q_n Q_T  Q_u=Q, Q_n Q_T =, Q_n Q_u =, Q_T Q_u =.

------34. Синтез конечных автоматов

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

 Введем основные понятия и определения.

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

состояний автомата, а так же множества входных и выходных сигналов конечны, то автомат называется конечным автоматом.

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

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

------35 Построение линейных оптимизационных моделей

ХЗ ХЗ

-----36 Алгоритм решения задачи линейного программирования на основе использования симплекс-метода

Симплекс-метод — алгоритм решения оптимизационной задачи линейного программирования путём перебора вершин выпуклого многогранника в многомерном пространстве. Метод был разработан американским математиком Джорджем Данцигом (George Dantzig) в 1947 году.