![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Тема 4. Мощность множества конечных автоматов.Стр 1 из 5Следующая ⇒
ЭЛЕМЕНТЫ Теории автоматов (теоретическая часть раздела) В.В. Гуренко Модуль 2. План. Мощность множества КА. Классы КА. Эквивалентные состояния автомата и их свойства. Минимальная форма автомата. Алгоритм получения минимального КА.
Тема 4. Мощность множества конечных автоматов.
Доказательство. Рассмотрим структуру таблицы переходов/выходов КА в общем виде (достаточно, например, только для автомата Мили в силу функциональной эквивалентности моделей Мили и Мура, рис. 4.1):
Ly yiÎ Y = {y1, y2, … yq} sjÎ S = {s1, s2, … sn} Ls
Рис. 4.1. Структура таблицы переходов/выходов КА
Всего способов заполнения одной подстроки подтаблицы переходов (Ls) –
всего возможных подтаблиц переходов
▄
|