---
title: "Regular expression with substring 0101"
subject: "Theory of Computation"
chapter: 2
key: "semester_3/theory_of_computation:re-substring-0101"
source: https://www.bctengineer.com/q/semester_3/theory_of_computation/re-substring-0101
site: BCT Engineering
---

# Regular expression with substring 0101

Theory of Computation · Chapter 2: Finite Automata

- Asked in: 2072 Chaitra
- Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14
- Page: https://www.bctengineer.com/q/semester_3/theory_of_computation/re-substring-0101
- Whole chapter: https://www.bctengineer.com/md/semester_3/theory_of_computation/chapter-2

## Question

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

## 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.

## Answer

**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.

## Check yourself

The answer's key points as multiple-choice questions, with the correct option and why.

1. Which regular expression gives strings containing 0101 as a substring?
   A. (0101)*
   B. (0+1)* 0101
   C. 0101 (0+1)*
   D. (0+1)* 0101 (0+1)*
   Answer: D. Any prefix, then 0101, then any suffix. (Key point: Answer)

2. Which string is in L?
   A. 1101011
   B. 0110
   C. 1100
   D. 010011
   Answer: A. 1101011 contains 0101 starting at position 3. (Key point: Membership)

3. Why is (0+1)* used at both ends?
   A. They force at least one 0
   B. u and v can be any binary strings, including empty
   C. They repeat 0101
   D. They force even length
   Answer: B. A string is in L when it equals u·0101·v. (Key point: Meaning)

## Related in Theory of Computation

- [DFA avoiding substring 10110](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Adfa-not-substring-10110) — Theory of Computation, chapter 2
- [Every RE has NFA; ε-NFA for bb(a∪b)*ab](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Are-to-nfa-bb-aub-ab) — Theory of Computation, chapter 2
- [Pumping lemma: a^(n²) not regular](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Apumping-square-not-regular) — Theory of Computation, chapter 2, asked 5×
- [Regular grammar to RE and FA](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Aregular-grammar-to-re-fa) — Theory of Computation, chapter 2
- [DFA for {00}*{11}* language](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Adfa-00-star-11-star) — Theory of Computation, chapter 2

## Related in other subjects

- [Regular expression and FSA: at least three b's](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Afsa-at-least-three-b) — Discrete Structure, chapter 2
- [Closure properties of regular languages](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Aclosure-properties-regular-language) — Discrete Structure, chapter 2, asked 2×
- [Interpret: forms of communication and sign language](https://www.bctengineer.com/question.md?key=semester_5%2Fcommunication_english%3Ainterpret-sign-language-communication) — Communication English, chapter 1
- [Interpret: book for second-language readers](https://www.bctengineer.com/question.md?key=semester_5%2Fcommunication_english%3Ainterpret-book-for-second-language-readers) — Communication English, chapter 1