Как минимизировать конечные автоматы? Душкин объяснит
HTML-код
- Опубликовано: 30 сен 2024
- Теперь рассмотрим процесс и алгоритм минимизации произвольного конечного автомата.
Заходите на мой ТГ-канал: t.me/drv_official - на нём много всего интересного: анонсы видео, истории и всякий сторителлинг, объявления о мероприятиях и всякое такое разное.
Курс «Основы искусственного интеллекта» на Udemy: bit.ly/3BD2I4W
#ИИ #ИскусственныйИнтеллект #Вычисление #Система #Видеошпаргалка #ИНС #РоманДушкин #ДушкинОбъяснит #ТеорияАвтоматов #ТеорияФормальныхАвтоматов #ТФА #Автоматы #Автомат #Автоматон #МатематическаяЛингвистика #Языки #ФормальныеЯзыки #ФормальныйЯзык #КлассификацияЯзыков #РегулярныеГрамматики #КонтекстноСвободныеГрамматики #КонтекстноЗависимыеГрамматики #КонечныйАвтомат #АвтоматМили #АвтоматМура #МашинаТьюринга #УниверсальнаяМашинаТьюринга #КвантоваяМашинаТьюринга #АвтоматСМагазиннойПамятью #КлеточныйАвтомат #ЭлементарныйАвтомат #ЭлементарныйКлеточныйАвтомат #Жизнь #ИграЖизнь #ЖизньБезСмерти #ДеньИНочь #Правило30 #Правило90 #Правило110 #Правило184 #Семена #АвтоматФонНеймана #СамовоспроизводящийсяАвтомат #МуравейЛэнгтона #Wireworld #Highlife #ЧервиПатерсона #ПесчанаяКуча #ТеорияХаоса #ТеорияИнформации #ТеорияАлгоритмов #ТеорияГрафов
Все видео канала по искусственному интеллекту: ruclips.net/video/n3wEM7P11kI/видео.html
Вы всегда можете обратиться к нам за консультациями.
И, кроме того, вы всегда можете написать мне в ТГ: @rdushkin
Изображение с доски: disk.yandex.ru/i/p881KfSiGJDxqg
Спасибо за урок, очень пригодился в университете!
Очень люблю такие комментарии :)
Приглашайте одногруппников, у меня куча всего полезного.
В примере, когда речь идет про 1-эквивалентность, состояния D и E не входят в один класс, потому что различаются, например, строкой 110, из D по 2 единицам мы вернемся в D, а из нее нет перехода по 0
Какой таймкод?
В примере, изначальный автомат не принимает строку 00, а минимизированный принимает. Получается они задают разные языки?
Да, тут в комментариях уже обратили на это внимание.
@@dushkin_will_explain Если, не объединять состояния B и C, чтобы оба автомата не принимали строку 00, но при этом оставить объединёнными состояния D и E, то всё равно выходят два разных автомата. Потому что в таком случае "минимизированный" автомат принимает строку 0101, а исходный нет. Выходит, исходный автомат изначально был минимизированным?
@@clashofclansbases745, ну где-то я накосячил :(
В примере, из состояний D и E нет перехода по 0, получается это недетерминорованный автомат, разве нет?
да, у меня это тоже вопрос вызвало, то есть из класса DE теперь нет перехода по символу 0
Детерминированным конечным автоматом называется такой автомат, в котором нет дуг с меткой ε, и из любого состояния по любому символу возможен переход не более, чем в одно состояние. То есть указанный автомат является ДКА
@@gs-xr6ez так переход по 0 не является переходом по пустому символу, и до образования класса DE, из Е был переход по символу 0 в состояние B, тогда из класса DE должен быть такой же переход и автомат останется детерминированным
Какой таймкод?