Теория автоматов Основные понятия, способы задания, типы автоматов

Абстрактный автомат X={x 1,x 2,...x n - входной алфавит, Y={y 1,y 2,...y p } - выходной алфавит, Q={q 1,q 2,...q m } - алфавит состояний.

Функционирование автомата q Q и x X в момент [t] y Y - функция выходов автомата φ. q Q и x X в момент [t] q Q - функция переходов автомата ψ. Последовательность очередных состояний автомата (q 1 [1]q 2 [2]q 3 [3]...) Последовательности выходных символов (y 1 [1]y 2 [2]y 3 [3]...) для последовательности символов (x 1 [1]x 2 [2]x 3 [3]...) разворачиваются в моменты дискретного времени t = 1,2,3,....

Модель автомата Автомат есть система U=, где X={x 1, x 2, …, x n } – входной алфавит; Y={y 1, y 2, …, y m } - выходной алфавит; Q={q 0,q 1, …, q s } - алфавит внутренних состояний; ψ (q, x): Q×XQ – функция переходов; φ (q, x):Q×XY – функция выходов.

Типы автоматов Конечные Синхронные, асинхронные Детерминированные, недетерминированные, вероятностные (стохастические) q=q 0 Q – инициальный автомат M =

Автоматное отображение b = М(q 0 ;a), М – автоматный оператор. 1. входное и выходное слова имеют одинаковую длину (свойство сохранения длины); 2. y i -ый символ выходного слова зависит от всей последовательности символов входного слова, до x i -го включительно; кроме того если a=a 1 a 2, то b=b 1 b Если каждый раз перед подачей входных сигналов автомат находится в одном и том же состоянии, то при совпадении в двух входных словах первых W 1 букв, в выходных словах первые W 1 букв также совпадут.

Автоматы Мили и Мура

С-автомат

Порождающий автомат X=Ø

Распознающий автомат Y=Ø q[ 1] = (q[ ];x[ ])

Комбинационный автомат Q=Ø y[ ] = (x[ ])

Способы задания автоматов Чтобы задать конечный автомат M, необходимо описать все элементы множества M = {Q, X, Y, ψ, φ}, т.е. необходимо описать входной, выходной алфавиты и алфавит состояний, а также функции переходов ψ и выходов φ. При этом среди множества Q = {q 0,q 1,…, q n } необходимо выделить начальное состояния q 0, в котором автомат находится в момент времени t = 0. Существует несколько способов задания работы автомата, но наиболее часто используются табличный и графический.

Табличный способ

Таблица соединений

Графический способ 1. для каждого символа x X есть дуга, исходящая из вершины q Q; 2. каждый символ x X у каждой вершины-истока q Q принадлежит только одной дуге; 3. если между двумя вершинами q Q существует несколько дуг, что может быть обусловлено переходом автомата из состояния q s Q в состояние q t Q при различных символах на входе, то есть x i x j, то эти дуги могут быть заменены одной дугой с указанием дизъюнктивной связи этих состояний (например, если y u y v, то на дуге следует указать (x i /y u &x j /y v );.если y u =y v =y, то - (x i &x j )/y).

Пример

Гомоморфизм =(f;g;h) формирует гомоморфное отображение модели автомата М 1 на модель автомата М 2 когда каждому значению x 1k X 1, y 1j Y 1 и q 1i Q 1 соответствуют единственные образы x 2k X 2, y 2j Y 2, q 2i Q 2.

Изоморфизм f -1 ;g -1 ;h -1 определяет гомоморфное отображение модели автомата М 2 на модель автомата М 1 когда каждому значению x 2k X 2, y 2j Y 2 и q 2i Q 2 соответствуют единственные образы x 1k X 1, y 1j Y 1, q 1i Q 1. Если найдена совокупность операторов ( ), для которой, то такое взаимное отображение называют изоморфным.

Задание Минимизировать функцию методом неопределенных коэффициентов Минимизировать функцию методом Квайна-Мак-Класки Минимизировать функцию с помощью карт Карно