Розширення функцій d і l

Функції d і l розширюються на множину пар вигляду “стан, вхідне слово в алфавіті Х”. Нехай р = <х₁,x₂,…x_r> - вхідне слово довжини “r”. Функцією заключного стану називається функція d(s_i, p), що визначає стан автомата, в якій він потрапляє через “r” тактів, пройшовши послідовно всі стани, визначені словом Р, функцією слова-стану є функція d^~(s_i, p), що визначає усі стани, через які автомат пройшов після подачі вхідного
слова р.

Для скрізь визначеного автомата функції d, d^~ завжди визначені. Для часткового автомата d, d^~ не визначені, якщо під дією вхідного слова автомат потрапляє хоча б в один невизначений стан.

Функцією заключного виходу називається функція l^~(s_i, p), що визначає значення функції виходу автомата після впливу на вхід слова p.

Реакцією l(s_i, p) автомата в стані s_i на вхідне слово p називається вихідне слово g автомата, що з'являється на виході в період дії вхідного слова p, тобто g = l(s_i, p).

Приклад. Нехай є вхідне слово p₁ = <x_1, x₁ x₂ x₁ x₁ x₂> для часткового автомата А з табл. 18.6. Тоді функція заключного стану d^~(s_1, p₁) = d^~(s_1, <x_1, x₁ x₂ x₁ x₁ x₂>) = s₂ – визначена, d^~(s_1, p₂) = =d^~(s_1, <x₁ x₁ x ₁ x₁ x₂>) – не визначена, функція заключного виходу має вид l^~(s_1, p₃) = l^~(s_1, <x₂ x₁ x_2, x₁>)=y₃, реакція виглядає l(s_1, p₁) = (y_1, y_3, ~, y_3, y_3, y₂), l(s_1, p₂) = <y_1, y_3, y_3, ~,~>, l(s_1, p₃) = (y_2, y_3, y_2, y₃).

Контрольні запитання

1. Що є абстрактним автоматом, у якому часі функціонує автомат?

2. Яка різниця між скрізь визначеним і частковим автоматом?

3. Що є скінченним та нескінченним автоматом?

4. Яка різниця між автоматами Мілі та Мура?

5. Які способи завдання автоматів існують?

6. Як у табличному способі задаються автомати Мілі та Мура?

7. Як у графічному способі задаються автомати Мілі та Мура?

8. Які розширення функцій d і l можливі?

9. Що є функціями заключного стану і слова-стану?

10. Що є функціями заключного виходу і вихідного слова?

Список літератури

Основна

18.1. Мелихов А.Н. Ориентированные графы и конечные автоматы. – М.: Наука, 1971. – С.154-182.

18.2. Брауэр В. Введение в теорию конечных автоматов. – М.: Радио и связь, 1987. - С.33-41, 74-82, 118-132.

18.3. Кук Л., Бейз Г. Компьютерная математика. – М.:Наука, 1990.-С.302-335.

Додаткова

18.4.Горбатов В.А. Основы дискретной математики. – М.: Высш.шк., 1986. - С.160-204.

18.5.Биркгоф Г., Барти Т. Современная прикладная алгебра. – М.: Мир, 1976. - С.75-80.

Для практичних занять

18.6. Методичні вказівки і завдання до контрольних робіт з дисципліни «Основи дискретної математики» для студентів очної та заочної форм навчання фахів 6.0804, 6.0915 / О.М. Мартинюк. – Одеса: ОНПУ, 2002. – С.49-52.

18.7. Гаврилов Г.П., Сапоженко А.А. Сборник задач по дискретной математике. – М.: Наука, 1973. - С.190-208.

Лекція 19. Синхронні та асинхронні автомати. Перетворення

Вступ

Лекція має за мету навести поняття синхронних і асинхронних автоматів Мілі і Мура. Розглянути стійки стани автомата Мура, стійки стани та виходи автомата Мілі, що дозволяють ввести синхронні та асинхронні автомати. Звернено увагу до перетворення автоматів Мілі та Мура, а також до моделі С-автомата.

У лекції присутні чотири підрозділи:

19.1. Синхронні й асинхронні автомати

19.2. Асинхронні автомати, що тактуються

19.3. Перетворення автоматів Мілі і Мура

19.4. Сполучена модель автоматів – С-автомат