---
title: "CFG for RE 0*1(0∪1)*"
subject: "Theory of Computation"
chapter: 3
key: "semester_3/theory_of_computation:cfg-regex-0star-1"
source: https://www.bctengineer.com/q/semester_3/theory_of_computation/cfg-regex-0star-1
site: BCT Engineering
---

# CFG for RE 0*1(0∪1)*

Theory of Computation · Chapter 3: Context Free Grammar

- Asked in: 2072 Chaitra
- Video: [RE to CFG,  Language to CFG | Theory of computation | TOC | Automata Theory](https://www.youtube.com/watch?v=8R5l-dJ5DNs) — MUEngineer
- Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14
- Page: https://www.bctengineer.com/q/semester_3/theory_of_computation/cfg-regex-0star-1
- Whole chapter: https://www.bctengineer.com/md/semester_3/theory_of_computation/chapter-3

## Question

Write a CFG for the regular expression R = 0*1(0∪1)*.

## Short answer

A CFG is S → A1B, A → 0A | ε, B → 0B | 1B | ε. Alternatively, S → 0S | 1B, B → 0B | 1B | ε. Both generate all strings with at least one 1.

## Answer

The regular expression 0*1(0∪1)* describes all binary strings that contain **at least one 1**: some 0's, then the first 1, then any string over {0,1}.

#### Grammar
G = (V, Σ, P, S) with V = {S, A, B}, Σ = {0, 1}, start symbol S, and productions:

```text
S → A 1 B
A → 0A | ε        (generates 0*)
B → 0B | 1B | ε  (generates (0∪1)*)
```

- A generates 0*, the leading zeros.
- The terminal 1 is the compulsory 1.
- B generates (0∪1)*, any tail.

#### Example derivation (string 00101)
S ⇒ A1B ⇒ 0A1B ⇒ 00A1B ⇒ 001B ⇒ 0010B ⇒ 00101B ⇒ 00101

#### Compact form
Merging A and B gives the equivalent grammar

```text
S → 0S | 1B
B → 0B | 1B | ε
```

Here S keeps producing leading 0's until the first 1 is produced, after which B generates anything. Both grammars generate exactly L(0*1(0∪1)*).

## Check yourself

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

1. What strings does 0*1(0∪1)* describe?
   A. Strings that end in 1
   B. Strings with exactly one 1
   C. All binary strings that contain at least one 1
   D. Strings that start with 0
   Answer: C. Leading zeros, a compulsory 1, then anything: the string contains at least one 1. (Key point: Language meaning)

2. Which grammar generates this language?
   A. S → A1B; A → 0A | ε; B → 0B | 1B | ε
   B. S → 0S1
   C. S → A1B; A → 1A | ε; B → 0B | ε
   D. S → 0S | 1
   Answer: A. A generates 0*, the terminal 1 is compulsory, and B generates (0∪1)*. (Key point: Grammar)

3. What does variable A generate?
   A. (0∪1)*
   B. 1*
   C. The leading zeros 0*
   D. Exactly one 0
   Answer: C. A → 0A | ε produces the zeros before the first 1. (Key point: Role of A)

4. In the compact grammar S → 0S | 1B, what does S do?
   A. Generates 1s until a 0
   B. Produces leading 0s until the first 1, after which B generates anything
   C. Produces equal 0s and 1s
   D. Generates only the empty string
   Answer: B. S keeps producing 0s; choosing 1B ends the leading zeros and B makes the tail. (Key point: Compact form)

## Related in Theory of Computation

- [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
- [Regular expression with substring 0101](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Are-substring-0101) — Theory of Computation, chapter 2
- [RE: even a's followed by odd b's](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Are-even-a-odd-b) — 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
- [RE: no more than 3 a's](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Are-at-most-3-as) — 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
- [Critical stress for Re > 400 and critical diameter](https://www.bctengineer.com/question.md?key=semester_4%2Fhydraulics%3Acritical-shear-stress-re-400-critical-diameter) — Hydraulics, chapter 10, asked 2×
- [Drag on sphere at Re = 0.2](https://www.bctengineer.com/question.md?key=semester_3%2Ffluid_mechanics%3Asphere-drag-low-reynolds) — Fluid Mechanics, chapter 9