Напишите регулярное выражение, описывающее множество

Question

L {w | w содержит любое количество подстрок 00 и 11, причем одна из них встречается в любом месте w}

Я предполагаю, что, поскольку 1 может быть где угодно, поэтому Σ*001Σ*1Σ*11Σ* должно быть регулярным выражением. Есть мысли или исправления?

Answer 1

Разбейте определение языка на части:

L := { w | 
  w contains any number of substrings 00 and 11
  w contains one "1"
}

Первая часть на самом деле ничего не значит. "Любое количество подстрок 00 и 11" не может содержать подстрок. Это не значит, что строка должна содержать хотя бы один из них. Это эквивалентно Σ*,

Вторая часть говорит, что строка должна содержать 1 где-то в этом: Σ*1Σ*