Это обычный язык или нет?

Question

У меня есть язык {4^(w⋅g)34^(g)|w,gεNAT} в алфавите {0,1}.

Мне нужно выяснить, является ли этот язык узнаваемым, разрешимым, контекстно-свободным, регулярным или ни одним из них.

Как бы я это сделал или узнал?

Спасибо

Answer 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* и, как таковой, ваш язык является регулярным, контекстно-свободным, разрешимым и узнаваемым.

Предположим, ваш язык не был регулярным;как ты мог сказать?Вы можете использовать теорему Майхилла-Нероде или лемму о накачке для регулярных языков, чтобы вывести противоречие из предположения, что язык регулярен.

Предположим, ваш язык не является контекстно-свободным.Вы можете использовать лемму о накачке для контекстно-свободных языков, чтобы вывести противоречие из предположения, что язык является контекстно-свободным.

Конечно, если бы ваш язык не был разрешим или узнаваем, вы также могли бы доказать это различными способами.