Реферат: Шпоры по теории автоматов

Билет №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,...

--> ЧИТАТЬ ПОЛНОСТЬЮ <--