Нужна помощь по рекурсивному определению для двух языков S* и T*, где S={aa,b} и T={w1,w2,w3,w4}

Question

В настоящее время я прохожу курс Теории автоматов, и у меня возникли следующие проблемы. Я пришел к ответу на 1-й вопрос, но смутился из-за постановки 2-го вопроса.

(i) Дайте рекурсивное определение для языка S*, где S = {aa,b}.

Шаг 1: Lamba, aa, b находятся в S.

Шаг 2: Если x находится в S, то bx и xb также.

Я хочу подтвердить мой подтвердить мой ответ.

И следующий вопрос, который меня полностью смущает, и я не могу найти ответ.

(ii) Дайте рекурсивное определение для языка T*, где T = {w1, w2, w3, w4}, где эти w являются некоторыми конкретными словами.

Answer 1

(Я) Очень близко. Вам не хватает хотя бы одного правила, и у вас есть одно правило, которое вам не нужно. Вам нужно либо xaa или же aax на шаге 2. Вам нужно только одно из правил, которые вы даете на шаге 2, а не оба. В противном случае это правильно. Минимальное рекурсивное определение:

1. лямбда в с
2. если x находится в S, то aax и bx находятся в S.

(ii) То же, что (i), только обобщенно. Ответ

1. лямбда в т
2. если x находится в T, то w1x, w2x, w3x, w4x находятся в T.