Этот язык регулярный или нет?
У меня есть язык {4^(w⋅g)34^(g)|w,g∈NAT} над алфавитом {0,1}.
Мне нужно выяснить, является ли этот язык узнаваемым, разрешимым, контекстно-зависимым, регулярным или ни одного из них.
Как мне поступить так или узнать?
Спасибо
1 ответ
Рассмотрим любую строку в форме 4^a 3 4^b, Можем ли мы найти w, g за наших a, b? Ну, мы знаем, что g должен равняться bи тогда мы можем выбрать w = a + g, поскольку a, b а также g натуральные числа, поэтому тоже должно быть w; ответ таков: да, для любой строки вида 4^a 3 4^b, у нас есть строка на вашем языке.
Язык всех строк формы 4^a 3 4^b описывается регулярным выражением 4* 3 4* и, как таковой, ваш язык является регулярным, контекстно-независимым, разрешимым и узнаваемым.
Предположим, ваш язык не был регулярным; как ты мог сказать? Вы можете использовать теорему Майхилла-Нерода или лемму прокачки для регулярных языков, чтобы вывести противоречие из предположения, что язык был регулярным.
Предположим, что ваш язык не был контекстно-свободным. Вы можете использовать лемму Pumping для языков без контекста, чтобы получить противоречие, предполагая, что язык не зависит от контекста.
Конечно, если ваш язык не может быть решаемым или узнаваемым, вы также можете доказать это различными способами.