W2. Множества, алфавиты, формальные языки, операции над языками

Автор

Manuel Mazzara

Дата публикации

29 января 2026 г.

1. Краткое содержание

1.1 Введение в множества

Множество — одно из самых фундаментальных понятий в математике и информатике. Множество — это хорошо определённая совокупность различных объектов, называемых элементами или членами. Говоря «хорошо определённое», мы имеем в виду, что должен быть ясный критерий: принадлежит объект множеству или нет — двусмысленности быть не должно.

Множества можно задать двумя основными способами:

1.1.1 Явное перечисление

Для конечных множеств или когда перечисление уместно, можно описать множество, перечислив все элементы в фигурных скобках. Например:

Эта запись говорит, что — множество, содержащее ровно числа 1, 2, 4 и 8 и не содержащее других элементов.

Для бесконечных или очень больших конечных множеств иногда используют многоточие, чтобы указать закономерность:

Однако такая запись может быть неоднозначной: разные люди могут по-разному понять закономерность.

1.1.2 Задание множества через свойство (нотация с предикатом)

Более надёжный способ — указать свойство, которому должны удовлетворять элементы. Это называется заданием через свойство (set comprehension) или определением множества предикатом:

неотрицательноецелоекратное

Читается: « — множество всех таких, что — неотрицательное целое кратное 3».

Вертикальная черта «» означает «таких, что». Такая запись яснее, потому что явно сформулировано правило принадлежности.

1.2 Основные обозначения и отношения между множествами
1.2.1 Принадлежность элемента

Чтобы записать, что элемент принадлежит множеству, используют символ (читается «принадлежит» или «лежит в»):

Утверждение истинно, потому что 2 действительно является элементом множества .

Чтобы записать, что элемент не принадлежит множеству, используют :

Это истинно, потому что 4 нет в этом множестве.

1.2.2 Пустое множество

Пустое множество, обозначаемое , — особое множество без элементов. Оно единственно: существует ровно одно пустое множество. Пустое множество является подмножеством любого множества (о подмножествах — ниже).

1.2.3 Подмножества

Множество — подмножество множества , пишут , тогда и только тогда, когда каждый элемент также является элементом . Иными словами, в нет ничего, чего не было бы в .

Пример: , потому что каждый элемент входит и в .

Важно: любое множество — подмножество самого себя. Пустое множество — подмножество любого множества.

1.2.4 Равенство множеств

Два множества равны, если и только если у них в точности одни и те же элементы. Математически тогда и только тогда, когда и . То есть:

  • каждый элемент должен быть в , и
  • каждый элемент должен быть в
1.3 Множества, элементами которых являются множества

Множества могут содержать другие множества как элементы. Например:

Множество состоит ровно из двух элементов, и оба — сами множества. Заметьте:

  • если , то (потому что — элемент )
  • однако (число 1 не является прямым элементом ; оно элемент элемента )

Различие между «» (элемент) и «» (подмножество) здесь принципиально.

1.4 Операции над множествами

Подобно тому, как числа можно складывать и умножать, над множествами можно выполнять операции и получать новые множества. Наиболее распространённые:

1.4.1 Объединение

Объединение двух множеств и , обозначается , — это множество всех элементов, принадлежащих или (или обоим):

Здесь «» — логическое «или».

Пример: если и , то . Хотя 2 и 3 встречаются в обоих множествах, в объединении перечисляем их один раз.

1.4.2 Пересечение

Пересечение множеств и , обозначается , — множество элементов, принадлежащих и , и :

Здесь «» — логическое «и».

Пример: если и , то . Это единственные элементы, лежащие в обоих множествах.

1.4.3 Разность

Разность множеств и , пишут (иногда ), — множество элементов из , не лежащих в :

Пример: если и , то . Остаются только элементы , которых нет в .

1.4.4 Объединение многих множеств

Объединение обобщается на любое число множеств. Если есть (возможно, бесконечно много), их объединение обозначают

или эквивалентно:

Это множество всех элементов, принадлежащих хотя бы одному из этих множеств.

1.5 Булеан (множество всех подмножеств)

По любому множеству можно построить новое множество из всех подмножеств . Оно называется булеаном (power set) , обозначается или иногда .

Пример: булеан :

В нём элементов. Вообще, если в ровно элементов, то в ровно элементов.

Почему обозначение ? Идея: у каждого из элементов два выбора (включить или исключить), всего подмножеств.

1.6 Алфавиты и строки

Алфавит — конечное множество символов. Алфавиты обычно обозначают греческой буквой . Например:

  • (двоичный алфавит)
  • (латиница)
  • (цифры)

Строка (также слово или последовательность) над алфавитом — конечная последовательность символов из этого алфавита. Повторения разрешены.

Примеры над :

  • — строка (длина 3)
  • — строка (длина 8)
  • — строка (длина 1)

Длина строки , обозначается , — число символов в строке.

Пустая строка, обозначается (эпсилон) или иногда , — единственная строка из нуля символов. По определению .

1.7 Множество всех строк

Для алфавита множество всех строк над (включая пустую) обозначают . Это бесконечное множество (если только не пусто).

Пример: для :

Обычно строки перечисляют по возрастанию длины: сначала длина 0, затем 1, затем 2 и т.д.

1.8 Конкатенация строк

Как числа складывают, так строки конкатенируют. Если и — строки, их конкатенация, запись (иногда ), — строка из символов , за которыми следуют символы .

Пример:

Важные свойства конкатенации:

  1. Ассоциативность: для всех строк. От расстановки скобок результат не зависит.
  2. Некоммутативность: вообще говоря, . Порядок важен!
  3. Нейтральный элемент: . Конкатенация с пустой строкой не меняет строку.

Степенную запись используют для повторной конкатенации: , и т.д.

1.9 Формальные языки

Язык — множество строк над алфавитом. Точнее, язык над — любое подмножество :

Языки могут быть конечными и бесконечными. Примеры:

  • над : множество всех двоичных строк длины 8 — язык:
  • над : множество всех строк, начинающихся с 0:
  • над : английские слова образуют язык
  • над : десятичные записи чисел образуют язык

Термин «язык» широк, потому что охватывает и естественные языки (например английский), и формальные конструкции (множества двоичных строк, синтаксис языков программирования).

1.10 Операции над языками

Поскольку язык — множество, к языкам применимы все операции над множествами. Кроме того, из строк можно строить новые языки.

1.10.1 Множественные операции над языками

Основные:

  • Объединение: — строки хотя бы в одном языке
  • Пересечение: — строки в обоих языках
  • Разность: — строки из , не лежащие в
  • Дополнение: — все строки над , не входящие в
1.10.2 Конкатенация языков

Если и — языки над одним алфавитом , их конкатенация:

Это множество всех строк, получаемых взятием строки из и приписыванием справа строки из .

Пример: если и , то:

Конкатенация языков в общем случае некоммутативна: обычно .

Есть тонкое замечание: если , то включение не обязано выполняться в обе стороны.

1.10.3 Степень языка

Степень языка получают повторной конкатенацией языка с самим собой. Для положительного целого :

раз

По определению — язык, состоящий только из пустой строки.

Пример: если , то:

Для алфавита величина — все строки точной длины :

1.10.4 Звезда Клини (замыкание Клини)

Звезда Клини — одна из важнейших операций в теории формальных языков. Для языка звезда Клини (замыкание Клини) определяется так:

Разберём определение:

  • берём ноль или больше строк из
  • конкатенируем их
  • — множество всех таких результатов
  • часть «ноль или больше» означает, что пустая строка всегда входит в (ноль строк даёт )

Пример: если , то:

Это все строки из символа , повторённого любое число раз (включая ноль раз — получается ).

Другой пример: если , то:

Звезду Клини называют «замыканием», потому что результат замкнут относительно конкатенации: если взять две строки из и склеить, снова получится строка из .

1.10.5 Плюс Клини

Связанная операция — плюс Клини, обозначение , как звезда, но без пустой строки:

Это одна или более конкатенаций строк из (хотя бы одна обязательна).

Пример: если , то:

Разница: в есть , в — нет.

1.11 Кратко о специальных обозначениях

Для алфавита и строки :

  • (по соглашению, любая строка в степени 0 — пустая строка)
  • раз (-кратная конкатенация с собой)
  • (все строки длины ровно над )
  • (все строки любой длины над )
  • (все непустые строки над )

2. Определения

  • Алфавит: конечное множество символов, обычно обозначается . Примеры: , или любое конечное множество различных символов.
  • Строка (также слово или последовательность): конечная последовательность символов алфавита, повторения разрешены. Длина строки , , — число содержащихся в ней символов.
  • Пустая строка: единственная строка без символов, обозначается (эпсилон). По определению .
  • Множество: хорошо определённая совокупность различных объектов — элементов. Множество определяется тем, какие объекты в него входят: для любого объекта либо он элемент, либо нет (без двусмысленности).
  • Элемент: объект, принадлежащий множеству. Пишем , если — элемент , и , если нет.
  • Подмножество: — подмножество , пишут , если каждый элемент также элемент . Любое множество — подмножество самого себя; пустое множество — подмножество любого множества.
  • Пустое множество: единственное множество без элементов, . Подмножество любого множества.
  • Равенство множеств: и равны () тогда и только тогда, когда у них одни и те же элементы, т.е. и .
  • Объединение множеств: — множество элементов, принадлежащих или (или обоим): .
  • Пересечение множеств: — элементы, принадлежащие и , и : .
  • Разность множеств: или — элементы из , не лежащие в : .
  • Булеан (power set): или — множество всех подмножеств , включая и само . Если , то .
  • Задание через свойство (set comprehension): способ задать множество свойством элементов: означает « — множество всех , для которых истинно ».
  • Язык: язык над — множество строк над , т.е. любое подмножество . Языки бывают конечными и бесконечными.
  • : множество всех строк над , включая пустую; .
  • Конкатенация строк: склейка двух строк конец-в-начало. Для строк и конкатенация (или ) — символы , затем символы . Ассоциативна, в общем случае не коммутативна.
  • Конкатенация языков: — все строки из строки из и строки из .
  • Степень языка: — -кратная конкатенация с собой. По соглашению .
  • Звезда Клини (замыкание Клини): — все строки, получаемые конкатенацией нуля или более строк из : . Всегда содержит .
  • Плюс Клини: — без пустой строки.
  • Дополнение языка: для над дополнение (или ) — все строки над , не входящие в : .
  • Мощность (cardinality): для конечного число — число элементов. Для бесконечных множеств мощность — более абстрактное понятие «размера».
  • Свободный моноид (free monoid): с операцией конкатенации строк (string concatenation). Моноид — множество с ассоциативной бинарной операцией и нейтральным элементом (здесь ). «Свободный» значит отсутствие дополнительных ограничений на склейку строк.

3. Формулы

  • Объединение:
  • Пересечение:
  • Разность:
  • Объединение семейства множеств: длянекоторого
  • Мощность булеана: если , то
  • Длина строки: — число символов в ;
  • Конкатенация строк: — символы , затем символы
  • Ассоциативность конкатенации: для всех строк
  • Нейтральный элемент конкатенации: для любой строки
  • Степень строки: раз при ;
  • Конкатенация языков:
  • Степень языка: длявсех;
  • Звезда Клини:
  • Плюс Клини:
  • Строки фиксированной длины:
  • Все строки над алфавитом:
  • Все непустые строки:
  • Дополнение языка:

4. Примеры

4.1. Определение множества по описанию (Лаба 2, Задание 1.1)

Определите множество неотрицательноецелоеи.

Показать решение

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

  1. Найти неотрицательные целые по условию: нужно и , значит .
  2. Построить одноэлементные множества:
    • при :
    • при :
    • при :
    • при :
    • при :
  3. Собрать их в :

Ответ:

4.2. Определение множества по описанию (Лаба 2, Задание 1.2)

Определите множество инеотрицательныецелые.

Показать решение

Ключевая идея: это множество всех неотрицательных целых линейных комбинаций 3 и 5. Нужно понять, какие неотрицательные целые представимы в виде .

  1. Перечислить элементы: подберём значения и :
    • :
    • :
    • :
    • :
    • :
    • :
    • :
    • и так далее…
  2. Какие числа представимы: можно показать, что любое неотрицательное целое, кроме 1, 2, 4 и 7, представимо в виде . Это связано с задачей Фробениуса для монет 3 и 5: наибольшая невыразимая сумма равна .
  3. Явная запись множества:

Ответ: (все неотрицательные целые, кроме 1, 2, 4 и 7)

4.3. Равенство множеств (Лаба 2, Задание 1.3)

Равны ли множества и ?

Показать решение

Ключевая идея: множество определяется только составом элементов, а не порядком перечисления.

  1. Элементы первого множества: в — 0 и 1.
  2. Элементы второго множества: в — 1 и 0.
  3. Сравнение: в обоих ровно элементы 0 и 1.
  4. Равенство: два множества равны тогда и только тогда, когда совпадают элементы. Значит .

Ответ: да, . Порядок в записи множества не важен.

4.4. Равенство и повторы (Лаба 2, Задание 1.4)

Равны ли множества и ?

Показать решение

Ключевая идея: в фигурных скобках повторы не создают «дополнительных» элементов; важны только различные элементы.

  1. Различные элементы первого множества: в встречаются 0, 1 и 2 — множество различных: .
  2. Различные элементы второго множества: в — снова .
  3. Сравнение: совпадают.
  4. Вывод: обе записи задают одно и то же множество.

Ответ: да, .

4.5. Построение булеана (Лаба 2, Задание 2.1)

Постройте булеан множества .

Показать решение

Ключевая идея: булеан содержит все подмножества, включая и само множество.

  1. Все подмножества :
    • без элементов:
    • по одному элементу: ,
    • оба элемента:
  2. Полнота: для каждого элемента выбор «включить / не включить»:
    • исключить и :
    • только :
    • только :
    • оба:
  3. Счёт: 2 элемента подмножества — перечислены все.

Ответ:

4.6. Построение булеана (Лаба 2, Задание 2.2)

Постройте булеан .

Показать решение

Ключевая идея: сначала упростить множество (объединение), затем перечислить подмножества.

  1. Объединение: .
  2. Подмножества :
    • 0 элементов:
    • 1 элемент: , ,
    • 2 элемента: , ,
    • 3 элемента:
  3. Счёт: 3 элемента подмножеств.

Ответ:

4.7. Построение булеана (Лаба 2, Задание 2.3)

Постройте булеан .

Показать решение

Ключевая идея: у одноэлементного множества ровно подмножества.

  1. Подмножества :

Ответ:

4.8. Операции и булеан (Лаба 2, Задание 2.4)

Постройте булеан .

Показать решение

Ключевая идея: сначала пересечение, затем булеан.

  1. Пересечение: элементы, лежащие в обоих множествах.
    • 0 только в первом — нет.
    • 1 в обоих — да.
    • 2 только в первом — нет.
    • 3 в обоих — да.
    • 4 только в первом — нет.
    • 5 только во втором — нет.
    • только во втором — нет.
    Итого:
  2. Булеан :

Ответ:

4.9. Операции и булеан (Лаба 2, Задание 2.5)

Постройте булеан .

Показать решение

Ключевая идея: сначала разность, затем булеан.

  1. Разность: элементы первого, которых нет во втором.
    • 0: в первом, не во втором — да.
    • 1: в обоих — нет.
    • 2: в первом, не во втором — да.
    • 3: в обоих — нет.
    Итого:
  2. Булеан :

Ответ:

4.10. Булеан пустого множества (Лаба 2, Задание 2.6)

Постройте булеан .

Показать решение

Ключевая идея: единственное подмножество пустого множества — само пустое множество.

  1. Подмножества : только .
  2. Счёт: 0 элементов подмножество.

Ответ:

4.11. Основы формального языка (Лаба 2, Задание 2.7)

Определите для любого алфавита .

Показать решение

Ключевая идея: — все строки длины ровно . Значит — строки длины 0.

  1. Строки длины 0: существует ровно одна — .
  2. Вывод:

Ответ: для любого алфавита .

4.12. Все строки заданной длины (Лаба 2, Задание 2.8)

Определите для .

Показать решение

Ключевая идея: — все двоичные строки длины 4.

  1. Число строк: на каждой из 4 позиций 0 или 1, всего строк.
  2. Перечисление:
    • с префиксом 00:
    • с префиксом 01:
    • с префиксом 10:
    • с префиксом 11:

Ответ:

4.13. Булеан алфавита (Лаба 2, Задание 2.9)

Определите для .

Показать решение

Ключевая идея: — множество всех подмножеств самого алфавита.

  1. Подмножества :
    • ,
  2. Счёт: 2 элемента 4 подмножества.

Ответ:

4.14. Булеан множества всех строк (Лаба 2, Задание 2.10)

Определите для .

Показать решение

Ключевая идея: бесконечно; — множество всех его подмножеств.

  1. Структура: — все конечные двоичные строки.
  2. : булеан бесконечного множества бесконечен (более того, мощность выше, чем у ).
  3. Примеры элементов :
    • (пустой язык)
    • множество всех строк, начинающихся с 0
    • множество всех строк чётной длины
    • любое другое подмножество

Ответ: — множество всех подмножеств (все возможные языки над ). Это несчётно бесконечное множество; говорят также о «» элементах в интуитивном смысле.

4.15. Алфавиты для языков (Лаба 2, Задание 3.1)

Укажите возможный алфавит для языка .

Показать решение

Ключевая идея: алфавит должен содержать все символы, встречающиеся в строках языка.

  1. Строки:
  2. Символы:
    • в «oh»: ,
    • в «ouch»: , , ,
    • в «ugh»: , ,
  3. Совокупность:
  4. Проверка: каждая строка составлена только из этих символов.

Ответ: например (или любое надмножество).

4.16. Алфавиты для языков (Лаба 2, Задание 3.2)

Укажите возможный алфавит для языка .

Показать решение

Ключевая идея: в алфавит входят все символы, встречающиеся в строках языка.

  1. Символы:
    • в «apple»:
    • в «pear»:
    • в «4711»:
  2. Без повторов:

Ответ: например (или любое надмножество).

4.17. Алфавиты для языков (Лаба 2, Задание 3.3)

Укажите возможный алфавит для языка всех двоичных строк.

Показать решение

Ключевая идея: двоичные строки используют только 0 и 1.

  1. Нужные символы: последовательности из нулей и единиц.

Ответ:

4.18. Звезда Клини на разных алфавитах (Лаба 2, Задание 3.4)

Что даёт при ?

Показать решение

Ключевая идея: — все строки (любой длины) над .

  1. Описание:
  2. Смысл: все конечные двоичные строки, включая пустую.

Ответ: (все двоичные строки любой длины)

4.19. Звезда Клини на разных алфавитах (Лаба 2, Задание 3.5)

Что даёт при ?

Показать решение

Ключевая идея: при одном символе в алфавите — все повторы этого символа.

  1. По длинам:
    • длина 0:
    • длина 1:
    • длина 2:
    • длина 3:
    • и т.д.
  2. Запись:

Ответ:

4.20. Звезда Клини от пустого алфавита (Лаба 2, Задание 3.6)

Что даёт при (пустой алфавит)?

Показать решение

Ключевая идея: без символов нельзя построить непустую строку; остаётся только пустая.

  1. Анализ: непустая строка требует хотя бы один символ из алфавита — их нет.

Ответ: (только пустая строка)

4.21. Определение алфавита (Лаба 2, Задание 4.1)

Для языка определите алфавит .

Показать решение

Ключевая идея: смотрим, какие символы встречаются в строках языка.

  1. Наблюдение: язык содержит все строки из символов 0 и 1.
  2. Алфавит: только 0 и 1.

Ответ:

4.22. Определение алфавита (Лаба 2, Задание 4.2)

Для языка определите алфавит .

Показать решение

Ключевая идея: какие символы появляются в языке.

  1. Наблюдение: все строки — повторы символа .

Ответ:

4.23. Дополнение языка (Лаба 2, Задание 4.3)

Пусть . Постройте дополнение для .

Показать решение

Ключевая идея: дополнение — все строки над , не входящие в .

  1. Определение:
  2. Описание: все двоичные строки, кроме 010, 101 и 11. В частности:
    • строки длины 1:
    • строки длины 2: (11 исключена)
    • строки длины 3, кроме 010 и 101:
    • все строки длины 4 и далее
  3. Явно:

Ответ: (все двоичные строки, кроме 010, 101 и 11)

4.24. Дополнение языка (Лаба 2, Задание 4.4)

Пусть . Постройте дополнение для .

Показать решение

Ключевая идея: нужно дополнение к языку «все строки, кроме 110».

  1. Исходный язык: — все двоичные строки, кроме 110.

  2. Дополнение:

    По теории множеств

  3. Проверка: разбивается на строки из и единственную строку 110.

Ответ:

4.25. Разность булеанов (Лаба 2, Задание 4.5)

Определите множество .

Показать решение

Ключевая идея: сначала булеаны, затем разность.

  1. :
  2. :
  3. Разность: элементы первого, отсутствующие во втором.
    • и — в обоих
    • — только в первом
    • — только в первом
  4. Результат:

Ответ:

4.26. Задание через свойство (Лаба 2, Задание 4.6)

Определите множество , где — множество всех неотрицательных целых.

Показать решение

Ключевая идея: это значения , для которых существует с .

  1. Условие: и .
  2. Перебор: .
    • …
  3. Итог:

Ответ:

4.27. Конкатенация языков (Лаба 2, Задание 5.1)

Пусть — язык над . Найдите и .

Показать решение

Ключевая идея: — пустая строка и строки из подряд идущих без . Нужны дополнение и звезда Клини.

(a) Дополнение :

  1. : — только , без .
  2. — все строки над , не из .
  3. Характеризация: строки, в которых есть хотя бы один .
  4. Запись: содержитхотябыодин

(b) Звезда Клини :

  1. Определение:
  2. Анализ: конкатенируем ноль или более строк вида , .
  3. Склейка:
  4. Вывод: сумма неотрицательных целых даёт любое неотрицательное целое в показателе:

Ответ:

  • содержитхотябыодин
4.28. Конкатенация языков (пример) (Лаба 2, Задание 5.2)

Пусть и над . Найдите .

Показать решение

Ключевая идея: — все склейки , , .

  1. Элементы: — 3 строки, — 2 строки.
  2. Все склейки:
  3. Без дубликатов:

Ответ:

4.29. Конкатенация языков (пример) (Лаба 2, Задание 5.3)

Пусть и над . Найдите .

Показать решение

Ключевая идея: раскрыть степени; .

  1. Явно:
  2. Все произведения:
    • , ,
    • , ,
    • , ,
  3. Результат:

Ответ:

4.30. Степень языка (Лаба 2, Задание 5.4)

Пусть . Найдите .

Показать решение

Ключевая идея: — все склейки двух строк из .

  2. Пары:
    • , ,
    • , ,
    • , ,
  3. Дубликатов нет.

Ответ:

4.31. Описание языка словами (Лаба 2, Задание 5.5)

Опишите словами язык над .

Показать решение

Ключевая идея: — звезда Клини двухсимвольного множества: все конечные склейки и .

  1. Нотация: — все строки из символов и .
  2. Состав:
    • длина 1:
    • длина 2:
    • длина 3:
    • и далее…

Ответ: язык всех конечных строк над алфавитом , включая пустую строку. Эквивалентно: все последовательности из и любой (конечной) длины.

4.32. Описание языка словами (Лаба 2, Задание 5.6)

Опишите словами язык над .

Показать решение

Ключевая идея: объединение двух звёзд Клини — строки только из или только из .

  1. :
  2. :
  3. Объединение:

Ответ: язык всех строк, состоящих либо только из , либо только из (пустая строка входит в оба слагаемых). Иными словами: строка не содержит одновременно символы и .

4.33. Описание языка словами (Лаба 2, Задание 5.7)

Опишите словами язык над .

Показать решение

Ключевая идея: в пересечении — то, что есть и там, и там.

  1. : строки без
  2. : строки без
  3. Пересечение: одновременно без и без — только .
  4. Итог:

Ответ: язык, состоящий только из пустой строки:

4.34. Описание языка словами (Лаба 2, Задание 5.8)

Опишите словами язык над .

Показать решение

Ключевая идея: разность языков, связанных с чётными повторами .

  1. : конкатенации строки «aa»: — все строки из чётной длины.
  2. : — длина делится на 4.
  3. Разность: в первом, но не во втором — чётная длина, не кратная 4.
  4. Характеризация: длины , т.е. длина

Ответ: строки из символов чётной длины, но с длиной не кратной 4. Примеры:

4.35. Раскрытие степенной записи (Лаба 2, Задание 5.9)

Запишите явно: .

Показать решение

Ключевая идея: степень — повторение строки или символа.

  1. : пять нулей:
  2. : три нуля и три единицы:
  3. : «010» два раза:
  4. : в формулировке задания опечатка; по смыслу имеется в виду и затем символ :
  5. : степень 0 даёт пустую строку:

Ответ:

  • (пустая строка)
4.36. Сложные операции над языками (Лаба 2, Задание 6.1)

Рассмотрим языки над :

Найти: 1. и 2. , , , ,

Показать решение

Ключевая идея: сначала уточним каждый язык.

  1. Языки:

    • — строки из одинаковых символов (все нули или все единицы, длина )

      Формально:

    • — все двоичные строки

    • —

    • —

    • — все непустые:

(Часть 1a: )

  • Значит

(Часть 1b: )

(Часть 2a: )

(Часть 2b: )

  • строки длины 1 в : только и

(Часть 2c: )

  • строки длины 2 в : только и

(Часть 2d: )

  • в нет , в все непустые

(Часть 2e: )

  • длина не может быть одновременно 1 и 2

Ответ: 1. и 2. - - - - -

4.37. Разность языков (Лаба 2, Задание 6.2)

Для тех же языков из упражнения 5 найти: 3. , , , ,

Показать решение

(Часть 3a: )

(Часть 3b: )

(Часть 3c: )

  • разные длины

(Часть 3d: )

  • все строки из непустые и лежат в

(Часть 3e: )

  • все непустые строки, кроме длины 2

Ответ: 3. - - - - - (все непустые строки, кроме длины 2)

4.38. Дополнения языков (Лаба 2, Задание 6.3)

Для тех же языков из упражнения 5 найти: 4. , , ,

Показать решение

(Часть 4a: )

  • в частности: содержитии

(Часть 4b: )

(Часть 4c: )

(Часть 4d: )

  • дополнение: пустая строка и все строки длины 2

Ответ: 4. - содержитии (пустая строка или «смешанные» строки) - - (пустая строка и строки длины не 1) - (пустая строка и все строки длины 2)

4.39. Конкатенация языков (Лаба 2, Задание 6.4)

Для тех же языков из упражнения 5 найти: 5. , ,

Показать решение

(Часть 5a: )

  • (все двоичные строки)
  1. Разбор: для каждой строки из (повтор одного символа) дописываем справа любую строку из .
  2. Примеры:
    • , :
    • , :
  3. Какие строки получаются? Докажем, что совпадает со всеми непустыми двоичными строками.
    • Для нужны и с — невозможно, так как в нет .
    • Если начинается с 0, пишем , где — любая строка. Возьмём и .
    • Если начинается с 1, пишем . Возьмём и .
  4. Итог:

(Часть 5b: )

  • (строки длины 1)
  • (строки длины 2)
  1. Все склейки:
  2. Результат: (все 3-битовые строки)

(Часть 5c: )

  • ,
  1. Все склейки:
  2. Результат: (все 3-битовые строки)

Ответ: 5. - (все непустые строки) - -

4.40. Звезда Клини и плюс (Лаба 2, Задание 6.5)

Для тех же языков из упражнения 5 найти: 6. , ,

Показать решение

(Часть 6a: )

  • (все двоичные строки)
  • — все конкатенации нуля или более строк из
  1. Разбор: любая склейка строк из снова даёт двоичную строку.
  2. Включения в обе стороны:
    • Любая строка из двоична? Да, так как сомножители из двоичны.
    • Любая двоичная строка лежит в ? Да: как одна конкатенация из .
  3. Итог:

(Часть 6b: )

  • (односимвольные строки)
  • — конкатенации нуля или более строк из
  1. Смысл: склеивая любое число символов 0 и 1, получаем любую двоичную строку.
  2. Проверка:
    • любая такая склейка — двоичная строка;
    • любую двоичную можно разбить на одиночные 0 и 1;
    • ноль сомножителей даёт .
  3. Итог:

(Часть 6c: )

  • (все строки длины 2)
  • — конкатенации нуля или более строк из
  1. Разбор: каждая строка в получается склейкой блоков длины 2.
    • ноль склеек:
    • одна склейка: любая строка из
    • две склейки: любая строка длины 4 из двух блоков по 2 символа
    • три склейки: длина 6
    • вообще: длины
  2. Наблюдение: строк длины 2 дают строку длины .
  3. Возможные длины: (пустая), , , … — все чётные длины.
  4. Итог: чётна (все двоичные строки чётной длины, включая )

Ответ: 6. - (все двоичные строки) - (все двоичные строки) - чётна (двоичные строки чётной длины, включая )

4.41. Минимальный алфавит по языку (Туториал 2, Пример 1)

Для языка начинаетсяс определите минимальный алфавит .

Показать решение

Ключевая идея: минимальный алфавит содержит все используемые символы и не содержит лишних.

  1. Язык: все строки, начинающиеся с цифры 0:
  2. Символы: нужен 0; после ведущего 0 могут идти любые символы алфавита.
  3. Минимум: чтобы были не только «0», нужен ещё хотя бы один символ; минимально — добавить 1.
  4. Проверка: при язык согласуется с описанием.

Ответ: минимальный алфавит (или любой двухсимвольный, где один символ — 0).

4.42. Ассоциативность и нейтральный элемент (Туториал 2, Пример 2)

Проверьте ассоциативность конкатенации и укажите нейтральный элемент.

Показать решение

Ключевая идея: показать и найти с .

Ассоциативность:

  1. Пусть , ,
  2. : , затем
  3. : , затем
  4. Вывод: .

Нейтральный элемент:

  1. : ,
  2. Вывод: нейтральный элемент — .

Ответ: конкатенация ассоциативна: . Нейтральный элемент — : для всех строк .