Это обычный язык или нет?
-
21-12-2019 - |
Вопрос
У меня есть язык {4^(w⋅g)34^(g)|w,gεNAT} в алфавите {0,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*
и, как таковой, ваш язык является регулярным, контекстно-свободным, разрешимым и узнаваемым.
Предположим, ваш язык не был регулярным;как ты мог сказать?Вы можете использовать теорему Майхилла-Нероде или лемму о накачке для регулярных языков, чтобы вывести противоречие из предположения, что язык регулярен.
Предположим, ваш язык не является контекстно-свободным.Вы можете использовать лемму о накачке для контекстно-свободных языков, чтобы вывести противоречие из предположения, что язык является контекстно-свободным.
Конечно, если бы ваш язык не был разрешим или узнаваем, вы также могли бы доказать это различными способами.