Билет №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),..., а(к) найдутся повторяющиеся состояния. АА используются для построения генераторов периодических последовательностей, генераторов синхросерий и в других задающих устройствах. Автомат без выхода: В таком автомате выходной алфавит содержит только одну букву. ............