Генерация множеств с помощью рекурсии - Язык и строки (CS / логика)

Question

Это общий логический вопрос, общий для большинства вводных языковых и машинных курсов. Тем не менее, я искал в Интернете и на форумах какую-либо помощь по этому вопросу, но, похоже, не могу найти тему, которая подробно описывает, что будут содержать последующие наборы. Вот пример вопроса: (У меня много таких проблем с HW, я просто не знаю с чего начать)

Пусть L будет языком над {a, b}, сгенерированным следующим рекурсивным определением базис: λ ∈ L рекурсивный шаг: если w ∈ L, то awbb находится в L. замыкание: строка w ∈ L, только если она может быть получена из базиса, заданного конечным числом приложений рекурсивного шага. Часть а. Дайте наборы L1; L2; и L3 генерируется рекурсивным определением. Обратите внимание, что L0 = λ

Я понял, что алфавит: {a, b}, Lo = пустая строка, и если строка w содержится в L, то awbb находится в L. Но что это значит для следующих наборов пары?

Я думаю, что L1 = {λ, awbb}, а затем L2 = {λ, awbb, aawbbwbb}?

Буду признателен за любую помощь, которую вы можете предложить.

Answer 1

Я думаю, что вы неправильно интерпретируете, что означает правило

Если w ∈ L, то awbb ∈ L

.Это не означает, что буквенная строка «awbb» находится в L. Вместо этого это означает, что если у вас есть некоторая строка w ∈ L, вы можете заменить эту строку w на строку awbb, и эта результирующая строка будет в L. ДляНапример, если ab ∈ L, то также aabbb ∈ L.

Используя это, попробуйте снова построить множества L ₁ и L ₂ .Я думаю, что вы обнаружите непосредственный паттерн, как только соберете первые несколько сетов.

Надеюсь, это поможет!