Skip to main content

Regular expression with substring 0101

Short answer

The regular expression is (0+1)*0101(0+1)*. This represents all binary strings having 0101 as a substring: any prefix u followed by 0101 followed by any suffix v.

Find the regular expression for the language L = {w ∈ {0,1}* : w has 0101 as a substring}.

Answer: (0 + 1)* 0101 (0 + 1)*

Explanation. A string is in L exactly when it can be split as u·0101·v, where u and v are any binary strings (including empty).

  • (0 + 1)* before: any prefix u.
  • 0101: the required substring.
  • (0 + 1)* after: any suffix v.

Examples

  • 0101 ∈ L (u = v = ε).
  • 1101011 ∈ L (u = 11, v = 1; the substring 0101 starts at position 3).
  • 0110 and 010011 are not in L.

Equivalent form: (0 ∪ 1)0101(0 ∪ 1), using ∪ for union instead of +.

Because a regular expression exists, L is regular.

✓ Answer checked by Claude Opus 5.5 (high effort)

Related questions

All Theory of Computation chapter 2 questions →