Является ли этот язык регулярным или нет?

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

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

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

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