Скачать или смотреть Преобразование NFA в DFA

Здесь мы показываем, что НКА и ДКА эквивалентны с помощью конструкции powerset. Идея заключается в том, что ДКА «симулирует» все возможные варианты выбора, которые может сделать НКА. Мы многократно отмечаем, в каких состояниях НКА может находиться в данный момент, и «объединяем» их все в одно. Мы повторяем это до тех пор, пока в ДКА не останется «неиспользованных» переходов.

Внести свой вклад:
Patreon:   / easytheory  
Discord:   / discord  

Прямая трансляция (по воскресеньям в 14:00 по Гринвичу, 2 часа):
Twitch:   / easytheory  
(также на YouTube)
Mixer: https://mixer.com/easytheory

Социальные сети:
Страница в Facebook:   / easytheory  
Группа в Facebook:   / easytheory  
Twitter:   / easytheory  

Товары:
Одежда Language Hierarchy: https://teespring.com/language-hierar...
Одежда Pumping Lemma: https://teespring.com/pumping-lemma-f...

Если вам нравится этот контент, пожалуйста, подпишитесь на мой канал:    / @easytheory  

Сторонники уровня Ultimate: (нет)
Сторонники уровня Diamond: (нет)
Сторонники уровня Platinum: (нет)
Сторонники уровня Gold: Аноним (x1), Мика Вуд, Бен Притчард
Сторонники уровня Silver: Тимми Гай
Сторонники уровня Yash Singhal

▶ДОПОЛНИТЕЛЬНЫЕ ВОПРОСЫ◀
1. Можете ли вы привести пример преобразования NFA в DFA, где будут выполнены все 2^n состояний DFA, независимо от условий?
2. Всегда ли DFA, полученный в результате преобразования, имеет минимальный размер?

▶ОТПРАВЬТЕ МНЕ ВОПРОСЫ ПО ТЕОРИИ◀
[email protected]

▶ОБО МНЕ◀
Я профессор компьютерных наук и увлечён теорией вычислительных систем. Я читал более 12 курсов в Университете штата Аризона и Университете Колгейт, включая несколько разделов теории для студентов бакалавриата.

▶ОБ ЭТОМ КАНАЛЕ◀
Теория вычислений, пожалуй, является фундаментальной теорией компьютерных наук. Она призвана математически определить, что такое вычисление, какие задачи можно решить с помощью компьютера, а какие — невозможно. Главная цель — дать математическое определение компьютера, не прибегая к реальным компьютерам, аппаратному и программному обеспечению, а также к множеству языков программирования, используемых нами сегодня. Понятие машины Тьюринга служит этой цели и определяет то, что, по нашему мнению, является основой всех вычислимых функций.

Этот канал также посвящен более слабым формам вычислений, уделяя особое внимание двум классам: регулярным языкам и контекстно-свободным языкам. Эти две модели помогают понять, что мы можем делать с ограниченными средствами вычислений, и предлагают богатую теорию, с помощью которой вы можете отточить свои математические навыки в рассуждениях с помощью простых машин и определяемых ими языков.

Однако они существуют не просто как слабая форма вычислений — их наиболее привлекательным аспектом является то, что сформулированные на них задачи поддаются решению, то есть мы можем строить эффективные алгоритмы для рассуждений с такими объектами, как конечные автоматы, контекстно-свободные грамматики и магазинные автоматы. Например, мы можем моделировать устройство (схему) как систему с конечным числом состояний и определять, удовлетворяет ли схема некоторому свойству (например, корректно ли она выполняет сложение 16-битных регистров). Мы можем моделировать синтаксис языка программирования, используя грамматику, и строить алгоритмы, проверяющие, соответствует ли строка этой грамматике.

С другой стороны, большинство задач, требующих свойств машин Тьюринга,
неразрешимы. Этот канал на YouTube поможет вам увидеть и доказать, что некоторые задачи, связанные с машинами Тьюринга, неразрешимы, то есть ни один компьютер, ни одно программное обеспечение не может их решить. Например, вы увидите, что не существует программного обеспечения, способного проверить, остановится ли программа на языке C при определённом входном сигнале. Доказать возможность чего-либо, конечно, непросто. Но доказать невозможность чего-либо — редкое явление в информатике, и это очень поучительно.