Regex Basics and Definitions: Operators, Worked Examples and Exam Patterns

A regular expression is short, but one misread operator can change the entire language. The safest approach is to build the notation from its definitions, make precedence explicit, and test every answer with carefully chosen strings. Here we will derive two expressions over Σ = {0,1} and finish with a repeatable checking method.

Regex basics: alphabet, strings, languages and base expressions

An alphabet is a finite set of symbols. Let Σ = {0,1}. A string is a finite sequence of symbols from that alphabet, such as ε, 0, or 101, where ε is the empty string. Its length is zero, so |ε| = 0, while |101| = 3.

A language is a set of strings over an alphabet. Σ* is the set of every finite binary string, including ε. This vocabulary also connects regex with the wider notes in CS Fundamentals for Exams & Placements.

The base regular expressions have exact meanings:

These objects are different. ∅ is an empty set, not a string. {∅} is a set containing that empty set, while {ε} is a language containing one string. In particular, ∅ does not contain ε.

We write L(r) for the language denoted by expression r. Therefore L(0) = {0}, L(0|1) = {0,1}, L(ε*) = {ε}, and L(∅*) = {ε}. The last result follows because zero repetitions are always allowed by a star.

Regex operators and precedence: union, concatenation and closure

Three operators build larger expressions:

• Union: r|s denotes every string in L(r) or L(s).

• Concatenation: rs joins one string from L(r) to one from L(s).

• Kleene star: r* allows zero or more concatenated strings from L(r).

Positive closure is often written r+ = rr*, meaning one or more repetitions. Some books use + for union, so always read the notation defined by the question.

Precedence is closure first, concatenation second, union last. Thus 0|10* means 0 | (1(0*)), not (0|1)0*. Compare the two:

• Strings of length <= 3 in L(0|10*): {0,1,10,100}.

• Strings of length <= 3 in L((0|1)0*): {0,1,00,10,000,100}.

The witnesses 00 and 000 occur only in the second list, so the expressions are not equivalent.

Worked regex example: binary strings that end in 01

Start from the condition instead of guessing. Any binary prefix is (0|1)*, and the required final two symbols are 01. The expression is therefore (0|1)*01.

Membership can be checked by decomposition. 01 = ε·01, 101 = 1·01, and 1101 = 11·01, so all three strings match. 1110 does not match because its final two symbols are 10. The empty string does not match because it has no required suffix. The star applies only to the arbitrary prefix.

The same language can be represented by an automaton. Finite Automata: DFA vs NFA and Subset Construction explains that representation and the conversion ideas around it.

Build a regex from a condition: an even number of 1s

Zeros may occur before, between, and after the 1s. After any initial zeros, one pair of 1s with arbitrary zeros around the pair is 10*10*. Repeating complete pairs gives:

0*(10*10*)*

For 0010100, choose the initial 0* as 00. Choose one repeated block as 1·0·1·00, which is 10100. Concatenating the pieces gives 00·10100 = 0010100. The string contains exactly two 1s, so it is accepted.

The expression also accepts ε by taking both stars zero times. It rejects 10101, which contains three 1s and cannot be partitioned into complete pairs.

The equivalent DFA needs only two states. qE means that an even count of 1s has been seen, while qO means the count is odd. Reading 0 preserves parity, and reading 1 flips it.

Regex equivalence: safe identities and counterexamples

The following identities are valid for languages:

• r|∅ = r

• rε = εr = r

• r∅ = ∅r = ∅

• r|r = r

• r* = ε|rr*

• (r|s)t = rt|st

• r(s|t) = rs|rt

Concatenation is not generally commutative. 01 and 10 denote different one-string languages.

Counterexamples expose false identities quickly. (0|1)* is not 0*|1* because 01 is in the left language but not the right. (01)* is not 0*1*: 0011 is in 0*1* but not (01)*, while 0101 is in (01)* but not 0*1*.

To disprove equivalence, find one separating witness. To support equivalence systematically, convert both expressions to finite automata and compare the accepted languages. For a proof-oriented continuation, read Regular Expressions and Pumping Lemma: Worked Proof.

Regex traps: empty language, star and misplaced wildcards

Suffix and substring conditions also differ. (0|1)*01 means ends in 01, while (0|1)*01(0|1)* means contains 01. The string 010 matches only the second expression. The string 1101 matches both.

Before evaluating an expression, rewrite it with explicit parentheses. In a Theory of Computation question, do not assume programming features such as wildcard dots, capture groups, or backreferences unless the question defines them.

How exams test regex and how to check an answer

Common conceptual tasks ask you to identify a language, test a string, choose an equivalent expression, construct a regex from a constraint, find a shortest accepted or rejected string, or relate a regex to a DFA or NFA.

Use this five-step check:

1. Confirm the alphabet.

2. Insert parentheses using precedence.

3. Test ε.

4. Test two positive witnesses.

5. Test two negative or boundary witnesses.

For (0|1)*01, 01 and 1101 are positive witnesses. ε and 1110 are negative witnesses. This small set checks the minimum suffix, a longer valid prefix, the zero-length boundary, and a near-miss ending.

Once the concept check is comfortable, use Regex and FA Equivalence MCQs: 10 Solved PYQs to practise applying it.

Regex basics: the short version and next step

A regex denotes a language. ∅, ε, and alphabet symbols are the base cases. Closure binds before concatenation, which binds before union. A witness string is often the fastest way to catch a false equivalence claim.

For a structured sequence from regular expressions through automata, continue with Theory Of Computation / Automata Theory. If you only need adjacent subject notes, the CS Fundamentals category linked earlier is the lighter route.

Now choose one language condition, write one candidate regex, and test it on ε, two matching strings, and two near-misses before converting it to an automaton.