Автоматное отображение, его свойства. Автономный автомат. Свойства его автоматного отображения

Автоматное отображение:

Множество всех слов входного алфавита называется входным словарем(A*), а V* называется выходным словарем. Если автомат S задан(нач. состояние q0), и при поступление A* он выдает V*, то говорят, что автомат S производит отображение A*->V*.

Свойства:

Пусть |a|- длина входного слова, |w|- длина выходного слова

1.|a|=|w|

2.Отсутствие предвосхищения

Разобьем входное слово a на начало и окончание a1 a2, выходное слово w разобьем на начало и конец той же длины w= w1 w2, где |a1|=|w1|. S(q0, a1)=w1, => начальное состояние выходного слова зависит только от начального состояния входного слова

Автономный автомат.

Автомат S – автономный, если его входной алфавит содержит только одну букву (A={a}) То есть с каждым тактом поступает один и тот же сигнал. Автономный автомат без входа. На диаграмме мура из каждого состояния выходит по 1 стрелки.

Свойства его автономного отображения:

Автономное отображение для автономного автомата, всегда представляет собой периодическое слово(с предпериодом), при этом, если длина слова равна r, то длина периода не больше чем r, а длина предпериода строго меньше r.

Эквивалентные состояния и эквивалентные автоматы. Теорема о существовании минимального автомата.

Эквивалентные состояния и эквивалентные автоматы.

2 состояния q1 и q2 называются эквивалентными, если при подачи любого слова на эти состояния, автомат выдает одинаковое выходное слово.

2 автомата s1 и s2 называются эквивалентными, если для каждого состояния в s1 найдется эквивалентное ему состояния в s2

Теорема о существовании минимального автомата:

Для каждого автомата S существует единственный (с точностью до изоморфизма) минимальный автомат

Алгоритм минимизации автомата.

Минимизация- нахождение автомата, эквивалентного данному, но имеющего наименьшее число состояний.

Алгоритм:

1. Разбиваем множество состояний q на классы 1-го порядка

2. Разбиваем Q на классы 2-го порядка

3. Классы 2-го порядка разбиваются на классы 3-го порядка. Алгоритм заканчивается, если на шаге k+1 мы получаем то же самое что и на шаге k

Получившиеся классы на шаге k образуют состояния минимального автомата.

Комбинационные и логические автоматы. Теорема о реализации логического автомата в виде СЛС.

6. Теорема о реализации произвольного абстрактного автомата в виде СЛС.

Построение СЛС:

1. Минимизация автомата

2. Кодирование алфавитов

3. Составление автоматной таблицы

4. Составление канонических уравнений (мин ДНФ)

5. Построение СЛС