Обозначения для конкатов в теории множеств

Question

Я работаю над домашней работой для класса теории автоматов.Пока что только доказательства, включающие регулярные выражения, не слишком сумасшедшие.Во всяком случае, мой вопрос заключается в том, какова правильная запись набора для конкатенации?Например, я знаю, что R + S будет таким же, как R union S, но я не могу вспомнить, что такое теория множеств, эквивалентная конкатенации.

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

Answer 1

Я полагаю, вы имеете в виду объединение регулярных множеств. Обычно либо сцепление , либо оператор dot обозначает объединение регулярных множеств. Та же запись применяется к регулярным выражениям. Например

• AB = A · B = {xy: x ∈ A и y ∈ B}

Формально регулярные множества образуют алгебру Клини, которая является идемпотентным полукольцом с оператором звезды Клини, удовлетворяющим совокупности аксиом. В алгебрах, подобных идемпотентному полукольцу, умножение обычно выражается через конкатенацию или оператор точки. Вот почему конкатенация регулярных множеств - операция умножения в алгебре Клини - обозначается конкатенацией или оператором точки. То же самое относится и к регулярным выражениям.

Answer 2

R + S - это не то же самое, что R union S, потому что строки не являются множествами.Строки находятся на алфавите , который является набором.(Хотя технически вы могли бы представить строку как набор упорядоченных пар (char, index)).

Вы должны просто сказать R + S, когда вы хотите объединить.Вы не можете объединять общие наборы.

Однако, вы можете объединить наборов строк .Для наборов строк U и V конкатенация , UV состоит из всех строк вида uv, где u - строка из U, а v - строка из V. Это немного похоже на перекрестное произведение.