Новости Словари Конкурсы Бесплатные SMS Знакомства Подари звезду
В нашей
базе уже
59876
рефератов!
Логин

Пароль

Шпоры по теории автоматов

Шпоры по теории автоматов.
Шпоры по теории автоматов Билет №1
Определение ЦА. Основные понятия теории автоматов: ЦА конечные, синхронные,

структурная теория автоматов.
ЦА - устройство, предназначенное для преобразования цифровой информации,
способное переходить под воздействием входных сигналов из одного состояния
в другое и выдавать выходные сигналы.
ЦА конечны, когда множество входных и выходных сигналов, а также число
входных и выходных каналов и множество состояний автомата конечны.
Синхронный ЦА – входные сигналы действуют в строго определенные моменты
времени при Т=конст, определяемые генератором синхронизирующих импульсов, в
которые возможен переход автомата из одного состояния в другое.
Асинхронный ЦА – Т <> конст и определяется моментами поступления входных
сигналов, а переход автомата из одного состояния в другое осуществляется
при неизменном состоянии входа.
Идеализированный ЦА – Не учитываются переходные процессы в элементах схемы
автомата, разница в фактических величинах Т для правильного
функционирования автомата не имеет значения, поэтому для описания законов
функционирования ЦА вводят абстрактное время, принимающее целые
неотрицательные значения.
Абстрактный ЦА - шестикомпонентный вектор S = {A,z,w,?,?,a1}, у которого:
А- множество состояний автомата, Z – входные сигналы, W- выходные сигналы,
?- функция переходов, ?- функция выходов, а1 – начальное состояние
автомата.
Структурный ЦА – учитывает структуру входных и выходных сигналов, а также
его внутреннее устройство на уровне структурных схем.
Структурная теория ЦА изучает общие приемы построения структурных схем
автоматов на основе элементарных автоматов.
Абстрактная теория ЦА – изучаются наиболее общие законы их поведения без
учета конечной структуры автомата и физической природы информации.

Билет №2
Варианты ЦА: автоматы Мили и Мура, С-автомат, автомат без памяти,
автономный автомат, автомат без выхода, управляющие и операционные
автоматы, микропрограммные автоматы.
Автомат Мили – a(t+1) = ? (a(t), z(t)); w(t) = ? (a(t), z(t)); a(0) = a1,
t= 0,1,2,...
Автомат Мура – a(t+1) = ? (a(t), z(t)); w(t) = ? (a(t)); a(0) = a1, t=
0,1,2,...
С-автомат: под абстрактным С-автоматом понимают математическую модель
цифрового устройства, определяемую восьмикомпонентным вектором S =
{A,Z,W,U,?,?1, ?2,a1}, где А- множество состояний, Z- входной алфавит, W-
выходной алфавит автомата Мили, U- выходной алфавит автомата Мура, ?-
функция переходов автомата, ?1- функция выходов автомата Мили, ?2- функция
выходов автомата Мура, а1 – начальное состояние.
Автомат без памяти(КС): Алфавит состояний такого автомата содержит
единственную букву, поэтому понятие функции переходов вырождается и
становится ненужным для описания работы автомата, т.е. выходной сигнал в
данном такте зависит только от входного сигнала того же такта и никак не
зависит от ранее принятых сигналов.
Автономный автомат: В таком автомате входной алфавит состоит из одной
буквы. Автомат задается четырьмя объектами: А, W, ?, ? с возможным
выделением начального состояния а1. Если автомат конечен и число его
состояний равно к, то среди значений а(1), А(2),…, а(к) найдутся
повторяющиеся состояния. АА используются для построения генераторов
периодических последовательностей, генераторов синхросерий и в других
задающих устройствах.
Автомат без выхода: В таком автомате выходной алфавит содержит только одну
букву. Автомат задается тремя объектами: А, Z, ?. Из функций, задающих
поведение автомата, сохраняется лишь функция переходов.
Управляющие и операционные автоматы: ОА реализует действия над исходной
информацией (словами), т.е. является исполнительной частью операционного
устройства, а УА управляет работой ОА, т.е. вырабатывает необходимые
последовательности управляющих сигналов в соответствии с алгоритмом
выполняемой операции. УА используются не только в операционных устройствах
вычислительной техники в системе УА-ОА, но и в разнообразных системах
автоматики по управлению технологическими процессами и объектами.
Микропрограммные автоматы: Алгоритм записываемый с помощью микроопераций и
логических условий, называется микропрограммой.

Билет №3
Автоматы Мили и Мура. С-автомат. Законы функционирования. Основные
различия.
Автомат Мили – a(t+1) = ? (a(t), z(t)); w(t) = ? (a(t), z(t)); a(0) = a1,
t= 0,1,2,...
Автомат Мура – a(t+1) = ? (a(t), z(t)); w(t) = ? (a(t)); a(0) = a1, t=
0,1,2,...
Эти автоматы различаются способом определения выходного сигнала. В
автомате Мили функция ? определяет выходной сигнал в зависимости от
состояния автомата и входного сигнала в момент времени t, а в автомате Мура
накладываются ограничения на функцию ?, заключающиеся в том, что выходной
сигнал зависит только от состояния автомата и не зависит от значения
входных сигналов. Выходные сигналы ЦА Мура отстают на один такт от выходных
сигналов ЦА Мили, эквивалентного ему.
С-автомат: под абстрактным С-автоматом понимают математическую модель
цифрового устройства, определяемую восьмикомпонентным вектором S =
{A,Z,W,U,?,?1, ?2,a1}, где А- множество состояний, Z- входной алфавит, W-
выходной алфавит автомата Мили, U- выходной алфавит автомата Мура, ?-
функция переходов автомата, ?1- функция выходов автомата Мили, ?2- функция
выходов автомата Мура, а1 – начальное состояние.
a(t+1) = ? (a(t), z(t)); w(t) = ? 1(a(t), z(t)); u(t) = ? (a(t)); a(0) =
a1, t= 0,1,2,...
Отличие С-автомата в том, что он одновременно реализует две функции выходов
?1 и ?2, каждая из которых характерна для модели Мили и модели Мура в
отдельности. От С-автомата легко перейти к автоматам Мили и Мура с учетом
возможных сдвигов выходных сигналов на такт, аналогично тому, как возможен
переход от автомата Мили к автомату Мура и наоборот. Много реальных
автоматов работает по модели С-автомата.

Билет №4
Системы канонических уравнений (СКУ) и системы выходных функций (СВФ).
Построение СКУ И СВФ для автоматов Мили и Мура.
СКУ и СВФ являются аналитической интерпретацией таблиц переходов и выходов
или графов ЦА. СКУ определяет функции переходов ЦА, а СВФ определяет
функции выходов ЦА.
Каждое состояние ЦА интерпретируется как событие, соответствующее множеству
переходов в это состояние: As(t+1) = v Zf(t)&Am(t). Для сокращения записи
СКУ и СВФ опускают знаки конъюнкции и времени t в правой части уравнения.
Для автомата Мили: СКУ: a1(t+1) = a1z1 v a2z2 v a4z2; a2(t+1) = a1z2;
a3(t+1) = a3z1 v a4z2; a4(t+1) = a2z1 v a3z2
CВФ: w1(t) = a1z1 v a1z2; w2(t) = a2z2; w3(t
Умар.Ш. был тут !!!!!
 
давайте изгоним мат !!!
 
ДОБРОЙ НОЧИ ОТ Ъ
ЛОКИ ИНО
 
ДМК МЭ
 
где инфааа?