Regular Expressions Formula Sheet: Rules, Worked Examples and Revision Notes
Remembering the symbols is only the first step. Use these identities, language templates and a complete ending-01 DFA example to check what a regular expression actually generates.
KnowledgeGate Team
Exam prep & CS education

Regular-expression errors usually begin before algebra: the language generated by each symbol is unclear. Union, concatenation, star, powers and identities become reliable when each is tied to the strings it generates. A language-to-expression derivation, a DFA trace and Arden equations make the checks concrete. For the wider CS path, use Learn.
Regular-expression symbols and precedence
An alphabet is a finite set of symbols, such as Sigma = {0,1}. A string is a finite sequence of those symbols; 01 has length 2. A language is a set of strings.
Keep epsilon and EMPTY separate. epsilon is the single empty string, of length 0; EMPTY is the empty language, containing no strings. Thus, L(epsilon) = {epsilon}, L(EMPTY) = EMPTY and L(0) = {0}.
Expression | Meaning and use |
|---|---|
R|S | Union: choose a string from either language. |
RS | Concatenation: choose from R, then from S, preserving order. |
R* | Concatenate zero or more strings from R. |
R^n | Exactly n concatenations; R^0 = epsilon. |
R+ = RR* | One or more repetitions; still allows epsilon if R generates epsilon. |
Union always uses | here. Precedence is star, concatenation, union. So 0|10* means 0|(1(0*)): it accepts 0, 1, 10 and 100, but rejects 00.
Regular-expression identities and simplification
Equality below means equality of generated languages, not identical written expressions.
Rule | When to use it |
|---|---|
R|EMPTY = R | Remove an empty alternative. |
R|R = R | Remove a duplicate alternative. |
Repsilon = epsilonR = R | Remove an empty-string factor. |
REMPTY = EMPTYR = EMPTY | Detect an impossible concatenation. |
R|S = S|R | Reorder alternatives. |
(R|S)|T = R|(S|T) | Regroup alternatives. |
(RS)T = R(ST) | Regroup concatenation without changing order. |
R(S|T) = RS|RT | Expand or factor a shared left part. |
(R|S)T = RT|ST | Expand or factor a shared right part. |
EMPTY* = epsilon; epsilon* = epsilon | Handle repetition when only epsilon can result. |
R* = epsilon|RR* = epsilon|R*R | Separate zero repetitions from further repetitions. |
(R*)* = R*; R*R* = R* | Collapse nested stars or adjacent identical starred factors. |
Use Regular Expressions in TOC: Rules and Worked Examples for notation, construction, NFA/DFA conversion and classical limits. Regex Design and Algebra Explained starts from constraints and proves a full expression with witness strings; the compact identity, ending-01 DFA and Arden direction here serve rapid revision.
Simplify (0|EMPTY)epsilon | 00* in three steps. First, 0|EMPTY = 0. Next, 0epsilon = 0, leaving 0|00*. Finally, 00* already includes 0 because its starred part can contribute epsilon, so the result is 00*.
It generates one or more zeros. Do not turn regrouping into reordering: concatenation does not generally satisfy RS = SR.
Language conditions to regular expressions
For Sigma = {0,1}, use these templates after identifying the exact condition.
Condition | Expression | Use and witness |
|---|---|---|
Starts with 1 | 1(0|1)* | Fix the first symbol; accepts 100. |
Ends with 01 | (0|1)*01 | Fix the suffix; accepts 1101. |
Contains 01 | (0|1)01(0|1) | Allow both surrounding parts; accepts 010. |
Exactly two 1s | 0*10*10* | Only zeros between fixed 1s; accepts 00100100. |
At least two 1s | (0|1)*1(0|1)1(0|1) | Allow extra 1s anywhere; accepts 111. |
Derive ends with 01 directly. The prefix can be any binary string, including epsilon, so write (0|1)*. Concatenate the mandatory suffix 01 to obtain (0|1)*01.
The minimum length is 2: an empty prefix contributes 0 symbols and the suffix contributes 2. Accepted examples are 01, 001, 101 and 1101. Rejected examples are epsilon, 0, 1, 010 and 111.
The prefix may itself contain 01. This expression fixes the final two symbols; it does not count occurrences of 01.
Ending-01 regular expression: three-state DFA check

A DFA for the same language remembers the longest suffix that is also a prefix of 01:
q0: no nonempty matching suffix; this is the start state.
q1: trailing 0.
q2: trailing 01; this alone is accepting.
State | Read 0 | Read 1 |
|---|---|---|
q0 | q1 | q0 |
q1 | q1 | q2 |
q2 | q1 | q0 |
Trace 1101: q0 ->1 q0 ->1 q0 ->0 q1 ->1 q2. The final state is q2, so accept.
Trace 010: q0 ->0 q1 ->1 q2 ->0 q1. The final state is q1, so reject.

Check acceptance after the full input. Passing through q2 is insufficient: the last 0 in 010 destroys the required suffix. This is precisely the difference between "ends with" and "contains". Regular Grammar and Finite Automata Explained starts from a right-linear grammar and converts it through NFA and DFA; the expression-first check here isolates what the ending-01 language means.
Arden's theorem: equation direction and traps
Arden's theorem solves language equations obtained from automata. If epsilon is not in L(A):
X = AX|Bhas the unique solutionX = A*B.X = XA|Bhas the unique solutionX = BA*.
If epsilon is in L(A), these remain the least solutions under set inclusion, but uniqueness is not guaranteed.
For X = 0X|1, the coefficient 0 cannot generate epsilon. Therefore X = 0*1 = {1,01,001,...}. Substitution gives 0(0*1)|1: either add a leading zero or take the base string 1.
For X = X0|1, the solution is X = 10* = {1,10,100,...}. Substitution gives (10*)0|1: append a zero or take 1. Hence 001 belongs only to the first solution, and 100 only to the second. Order matters.
Test a short distinguishing string before accepting a supposed identity:
(0|1)*differs from0*|1*: 01 belongs only to the former.(01)*differs from0*1*: 001 belongs only to the latter.01differs from10: the string 01 distinguishes them.
Regular-expression exam checks
IIT Guwahati's GATE 2026 CS syllabus lists regular expressions and finite automata in Section 6. These are original revision checks, not official past questions:
Does
0*10*10*accept 1010? Yes: its factors are epsilon, 1, 0, 1, 0. Does it accept 111? No, exactly two 1s are allowed.Are
(0|1)*01and(0|1)*01(0|1)*equivalent? No. The string 010 is rejected by the first and accepted by the second.Does
(01)*accept epsilon? Yes, through zero repetitions.
Translate the language into words, test epsilon and the shortest strings, then seek a counterexample or verify with an automaton. Passing a finite sample alone does not prove equivalence.
Regular-expression revision: short version and next step
Union chooses, concatenation preserves order, and star allows zero repetitions. Separate EMPTY from epsilon, and suffix conditions from substring conditions.
Try this 10-minute self-check: spend 2 minutes rebuilding the symbol table, 3 deriving the ending-01 expression, 3 tracing 1101 and 010, and 2 solving X = 0X|1. Explain each answer in words before checking the formulas.
For a full Theory of Computation sequence, use GATE CS Theory of Computation Course | PYQs.
Keep learning
Lexical Analysis Formula Sheet: Tokens, Regular Expressions and DFA Revision Notes
Keep the rules that matter under time pressure in one place, then apply them to regex counting, DFA construction, a 17-character scanner trace, and fallback.
Regular Language Properties: Formula Sheet and Revision Notes for GATE CS
Keep each regular-language rule beside its conditions. Revise identities, trace a product DFA and practise the quantifier order that makes a pumping-lemma proof work.
C Fundamentals Formula Sheet for GATE CS: Rules, Traces and Revision Notes
Revise the C rules that most often change an answer. Use compact tables, worked traces, address formulas, memory notes, and a practical error checklist.
Storage Classes, Structures and Enums in C: Formula Sheet with Worked Revision
Revise C declarations through three separate axes, then test them with a two-call trace, a byte-layout calculation and an enum sequence.





