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

Question

L {w |w содержит любое количество подстрок 00 и 11, причем одна из 1 встречается в любом месте 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Σ*