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

The regular expression 01(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:

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

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(01(0∪1)).