Регулярные языки, закрытые относительно подпоследовательностей

Описание: (Easy Theory теперь работает на скорости 60 кадров в секунду!) Здесь мы рассмотрим задачу демонстрации замкнутости регулярных языков относительно подпоследовательностей (т.е. подстроки, которая не обязательно должна быть непрерывной). Идея состоит в том, чтобы «устранить» переходы в исходном DFA, введя эпсилон-переходы для каждого существующего перехода. Мы также приводим конкретный пример.

#easytheory #nfa #dfa #gate #gateconcept #theoryofcomputing #turingmachine #nfatoregex #cfg #pda #undecidable #ricestheorem

Поучаствовать:
Patreon:   / easytheory  
Discord:   / discord  

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

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

Товары:
Одежда с символикой языковой иерархии: https://teespring.com/language-hierar...
Одежда Pumping Lemma: https://teespring.com/pumping-lemma-f...

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

Сторонники уровня Ultimate: (нет)
Сторонники уровня Diamond: (нет)
Сторонники уровня Platinum: (нет)
Сторонники уровня Gold: Anonymous (x1), Micah Wood, Ben Pritchard
Сторонники уровня Silver: Timmy Gy
Сторонники уровня Yash Singhal

▶ДОПОЛНИТЕЛЬНЫЕ ВОПРОСЫ◀
1. Что насчёт «суперпоследовательностей»? (т.е. все строки, содержащие строку w в L в качестве подпоследовательности)
2. Что насчёт подстрок?

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

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

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

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

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

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