Определение регулярного множества

Определим над множествами цепочек символов из алфавита V операции конка­тенации и итерации следующим образом:

РQ - конкатенация PÎV* и QÎV*: PQ, = {pq | "pÎP, "qÎQ.};

Р* - итерация PÎV*: Р* ⁼ {р* | "pÎP}.

Тогда для алфавита V регулярные множества определяются рекурсивно:

1. Æ — регулярное множество.

2. {l} — регулярное множество.

3. {а} — регулярное множество "aÎV.

4. Если Р и Q, — произвольные регулярные множества, то множества PÈQ, PQ и Р* также являются регулярными множествами.

5. Ничто другое не является регулярным множеством.

Фактически регулярные множества — это множества цепочек символов над за­данным алфавитом, построенные определенным образом (с использованием опе­раций объединения, конкатенации и итерации).

Все регулярные языки представляют собой регулярные множества.

Предлагаю ознакомиться с аналогичными статьями: