Регулярные языки и доказательства (модели вычислений)

Question

Мне нужна помощь с несколькими вопросами HW, которые я получил для своих моделей вычислений. Я прочитал соответствующие главы в тексте («Введение в теорию вычислений» Майкла Сипсера), но я чувствую, что эти вопросы HW требуют знания, которое книга мне не дала ... Первый вопрос:

(1) Докажите, что языка L не существует, что L * = {a} * {b} * Подсказка заключается в использовании противоречия.

Очевидно, что правая сторона является регулярным выражением; ноль или более а, за которыми следуют ноль или более. Это также может быть пустой эпсилон строки.

У меня возникла проблема с L *. У меня есть абсолютно нет подсказки, что a * применяется к языку, или как работать с этим уравнением из-за * на языке L.

Любая помощь или ресурсы по этому вопросу будут оценены.

=====

Второй вопрос проще, и я чувствую, что могу это сделать практически. Я могу оправдать это для себя, поэтому я думаю, что проблема заключается в том, чтобы писать это формально. Второй вопрос в том, что:

(2) Докажите, что если A и V являются языками над одним и тем же алфавитом (сигма) и A (является подмножеством) B, то A * (является подмножеством) B * , Подсказка - использовать индукцию.

Теперь, очевидно, (к примеру), если сигма = {1, 0}

и A = {00, 01, 10, 11}

и В = {00, 01, 10, 11, 100, 101, 110, 111}

Тогда что-нибудь в A * закрыто под B *, потому что B = A + некоторые другие вещи ... Если кто-то может помочь мне формализовать это в индуктивной форме, я был бы признателен.

Благодаря

Answer 1

(1) Вот полезный рекурсивное определение L*:

1. эпсилон в L*
2. если x находится в L, x в L*
3. если x и y находятся в L*, а также xy
4. L* является наименьшим язык, удовлетворяющий 1. - 3. для данного L

Учитывая это определение, вот доказательство от противного: предположим, R* = a*b*. Затем ab находится в R*. На 3., abab также должно быть в R*. Но тогда R* != a*b*, противоречие. Таким образом, R* = a*b* должен быть ложным; другими словами, для языка нет R является R* = a*b*.

Интуиция довольно проста: L* - это язык всех строк, которые могут быть образованы путем конкатенации нуля или более (с допустимыми повторами) строк от L. Рекурсивное определение работает, разрешая нулевые строки (в 1.), причем строки берут ровно одну строку из L (в 2.) и строки, образованные путем объединения потенциально многих строк от L (в 3).

(2) Используя определение, приведенное выше, мы индуктивно продолжаем число конкатенированных строк в A*. Для 0 конкатенаций пустая строка находится в A* и B*, поэтому мы хорошо (см. Правило 1.). Для 1 конкатенации, поскольку A является подмножеством B, строки в A будет A* (см правило 2.), и stringsfrom B будет B* (то же самое правило), поэтому все строки, принимающие один конкатенацию в A* также в B* , Теперь предположим, что все строки, принимающие k конкатенаций в A*, также находятся в B*. Как насчет струн, принимающих k+1 конкатенаций в A*? Ну, они формируются с использованием правила 3 ​​по строкам x и y в A*, принимая строго менее k+1 конкатенаций, то есть не более k конкатенаций. Другими словами, любая строка в A* с k+1 конкатенации можно переписать в виде xy, где x и y находятся в A* и x и y принимают в большинстве k сцеплений. Поскольку все строки в A*, принимающие не более k конкатенаций, также находятся в B* (по нашей гипотезе), мы имеем, что x и y находятся в B *. По правилу 3. xy также должен быть в B*. Поэтому строки, принимающие k+1, объединяются в A*, также должны принадлежать B*. Это завершает доказательство.

Примечание: этот блеск над некоторыми деталями и не является ужасно формальным, но вы должны получить идею и, надеюсь, сможете ее сформировать. Если вам нужно что-то более отполированное, сообщите мне, и я могу попытаться работать с вами на этом.