Итак, у меня есть эти вопросы, по которым мне нужна помощь. Я должен доказать, что это обычные языки. Я понятия не имею, что такое DSQ или DF в вопросе 3 и 4. У меня есть книга «Intro to Comp Theory by Spiser», но я не нашел ничего, что упоминало бы DSQ или DF.
1) L = {w....w ∈ Σ*} Σ = {a,b}
2) Trancate(n) = {wa^n w ∈ Σ* a ∈ Σ |w|=n}
3) DSQ = {a^p, b^p: p простое}
4) DF = {a^n b^n: n > или равно 0}
Все четыре из этих языков не являются регулярными. Есть несколько различных методов, которые вы можете использовать, чтобы доказать, что языки не являются регулярными. Вот выборка:
Используйте лемму накачки для обычных языков. Это наиболее распространенный метод доказательства того, что языки нерегулярны. Вы упомянули, что у вас завалялась копия Сипсера, и он хорошо изложил эту тему в Главе 1.
Используйте теорему Myhill-Nerode. Эта мощная теорема немного сложнее, чем лемма о накачке, но выполняет двойную функцию как инструмент для доказательства того, что языки не являются регулярными, и обеспечивает превосходную интуицию, которую вы можете использовать для обнаружения нерегулярных языков. (Это техника, которой я обучаю своих студентов во введении в теорию CS). Связанные слайды содержат доказательство того, что { an bn | n в N } не является регулярным, как из первых принципов, так и с использованием Myhill-Nerode.
Используйте свойства замыкания обычных языков. Часто можно показать, что язык не является регулярным, доказав, что после применения определенной операции, отображающей регулярные языки в регулярные языки, вы получите нерегулярный язык.
Просматривая приведенные вами примеры, я думаю, что лемма о накачке была бы самым простым способом доказать, что язык (1) нерегулярен. Теорема Майхилла-Нероде должна быстро справиться с (3) и (4). Для (2) вы можете рассмотреть возможность пересечения языка и bab, а затем применить Myhill-Nerode или прокачку лемма к этому результирующему языку.
