Regular Expressions: short notes (Theory of Computation)

Introduction

A regular expression (RE) is a concise notation for a language built from single symbols by union, concatenation and Kleene star. The languages denoted by regular expressions are exactly the regular languages, which are also exactly the languages recognized by finite automata (proved in Equivalence of Regular Expressions and Finite Automata).

In GATE, regular expressions appear as: simplify an expression, decide whether a string matches, convert between RE and DFA/NFA, or identify which expression denotes a given language. This note covers syntax, semantics, precedence, algebraic identities and worked matching examples. Conversion algorithms live in the equivalence note.

Prerequisites

Alphabets, Strings and Languages: $\Sigma^*$ , concatenation, star, $\emptyset$ versus $\{\varepsilon\}$ .

Core concepts

Inductive definition

Fix an alphabet $\Sigma$ . The regular expressions over $\Sigma$ and the language $L(r)$ of each expression $r$ are defined together.

Base cases.

$\emptyset$ is a regular expression, and $L(\emptyset) = \emptyset$ .
$\varepsilon$ is a regular expression, and $L(\varepsilon) = \{\varepsilon\}$ .
For every $a \in \Sigma$ , $a$ is a regular expression, and $L(a) = \{a\}$ .

Inductive cases. If $r$ and $s$ are regular expressions, then so are $(r+s)$ , $(rs)$ and $(r^*)$ , with

L(r+s) = L(r) \cup L(s), \qquad L(rs) = L(r)L(s), \qquad L(r^*) = (L(r))^*.

Some texts write $r \mid s$ or $r \cup s$ for union; these notes use $+$ , matching Hopcroft-Motwani-Ullman.

Parentheses. Parentheses are part of the syntax. They may be dropped using the precedence rules below.

Precedence and associativity

Operator precedence, from highest to lowest:

Kleene star $*$ (and usually $^+$ , if used as shorthand for $rr^*$ ).
Concatenation (juxtaposition).
Union $+$ .

Star is unary postfix and associates to the left in stacks of stars ( $a^{**} = (a^*)^*$ ). Concatenation and union are associative: $L((rs)t) = L(r(st))$ and $L((r+s)+t) = L(r+(s+t))$ . Union is commutative; concatenation is not.

Examples of parsing.

Written	Parsed as	Not
$a+b^*$	$a+(b^*)$	$(a+b)^*$
$ab^*$	$a(b^*)$	$(ab)^*$
$a+bc$	$a+(bc)$	$(a+b)c$
$(a+b)^*$	star of union

Misreading $a+b^*$ as $(a+b)^*$ is an error to avoid: the first language is $\{a\} \cup b^*$ ; the second is all strings over $\{a,b\}$ .

Shorthand

$r^+ = r r^*$ (one or more).
$r^? = r + \varepsilon$ (optional), used in some tools; not required in the formal definition.
$r^k$ means $r$ concatenated $k$ times ( $r^0 = \varepsilon$ ).

Unix-style character classes and wildcards (., [0-9]) are Related material from lexical analysis tools; the formal GATE RE uses only $\emptyset$ , $\varepsilon$ , symbols, $+$ , concatenation and $*$ .

How it works

Evaluating membership

To decide whether $w \in L(r)$ , expand the expression by the inductive definition, or convert to an NFA and run it (see the equivalence note). For small expressions, case analysis works:

$w \in L(r+s)$ iff $w \in L(r)$ or $w \in L(s)$ .
$w \in L(rs)$ iff $w = uv$ for some $u \in L(r)$ , $v \in L(s)$ .
$w \in L(r^*)$ iff $w = u_1 \ldots u_k$ for some $k \ge 0$ and each $u_i \in L(r)$ (the case $k = 0$ gives $\varepsilon$ ).

Algebraic identities

The following hold for all regular expressions $r,s,t$ (language equality):

Identity	Form
Associativity	$r+(s+t) = (r+s)+t$ , $r(st) = (rs)t$
Commutativity of $+$	$r+s = s+r$
Identities	$r+\emptyset = r$ , $r\varepsilon = \varepsilon r = r$
Annihilator	$r\emptyset = \emptyset r = \emptyset$
Idempotence	$r+r = r$
Distributivity	$r(s+t) = rs+rt$ , $(s+t)r = sr+tr$
Star	$\emptyset^* = \varepsilon$ , $\varepsilon^* = \varepsilon$ , $(r^)^ = r^$ , $r^ = \varepsilon + r r^* = \varepsilon + r^* r$
More star	$(r+s)^* = (r^* s^)^$ , $r(sr)^* = (rs)^* r$

These are proved by induction on expressions or by automata equivalence. The last row is useful when simplifying nested stars.

Test for an identity. A law $E = F$ whose variables $r, s, \ldots$ stand for arbitrary languages holds iff it holds after replacing each variable by a distinct fresh symbol and comparing the two resulting concrete expressions (Hopcroft-Motwani-Ullman, Section 3.4.7). So $(r+s)^* = (r^* s^*)^*$ is a law because $(a+b)^* = (a^* b^*)^*$ over $\{a,b\}$ , and $(rs)^* = r^* s^*$ is not, because abab is in $L((ab)^*)$ but not in $L(a^* b^*)$ .

Equivalence traps

Claim	True?	Witness or reason
$(a+b)^* = (a^* b^)^ = (a^* b)^* a^*$	yes	every string is blocks of $a$ s and $b$ s
$a^(b a^)^* = (a+b)^*$	yes	cut before each $b$
$(ab)^* a = a(ba)^*$	yes	shifting law $r(sr)^* = (rs)^* r$
$(aa)^* a = a (aa)^*$	yes	both are odd numbers of $a$ s
$r^* r^* = r^$ , $(r^)^* = r^$ , $(\varepsilon + r)^ = r^*$	yes	star absorbs
$\varepsilon + a a^* = a^*$	yes	$r^* = \varepsilon + r r^*$
$(a+b)^* = a^* + b^*$	no	`ab` is only on the left
$(ab)^* = a^* b^*$	no	`aab` only right, `abab` only left
$(a^* b)^* = (a+b)^*$	no	`a` only right: $(a^* b)^*$ is $\varepsilon$ or ends in $b$
$(a+b)^* a (a+b)^* b (a+b)^* = (a+b)^* ab (a+b)^*$	yes	an $a$ before a later $b$ forces an adjacent `ab`
$a^* \cap b^* = \emptyset$	no	both contain $\varepsilon$ , so the intersection is $\{\varepsilon\}$

Writing expressions for standard languages

Over $\{a,b\}$ :

Language	One correct expression
even length	$((a+b)(a+b))^*$
length divisible by 3	$((a+b)(a+b)(a+b))^*$
exactly two $a$ s	$b^* a b^* a b^*$
at most one $a$	$b^* (\varepsilon + a) b^*$
even number of $a$ s	$b^* (a b^* a b^)^$
no two consecutive $a$ s	$(b + ab)^* (\varepsilon + a)$
does not contain `ab`	$b^* a^*$
first and last symbols differ	$a(a+b)^* b + b(a+b)^* a$
ends with `ab`, alternative form	$(b^* a^+ b)^+$ where $r^+ = r r^*$

Counting check. The number of strings of length $n$ with no two consecutive $a$ s is the Fibonacci number $F_{n+2}$ (with $F_1 = F_2 = 1$ ): 1, 2, 3, 5, 8, 13 for $n = 0, \ldots, 5$ . A quick count of short strings is a reliable way to catch a wrong expression.

Algorithms and pseudocode

Simplification is not unique; a practical greedy strategy:

Text

SIMPLIFY-RE(r)
1  rewrite nested stars: (r*)* -> r*
2  drop empty unions: r+emptyset -> r
3  drop empty concatenations: r emptyset -> emptyset
4  factor where obvious: rs+rt -> r(s+t)
5  apply r* = epsilon + r r* when it shortens a case split
6  return the rewritten expression

There is no canonical "simplest" RE in general (two minimal-state DFAs are unique up to renaming, but many REs can denote the same language). Distinct regular expressions can denote the same language; follow any syntax or form required by the question.

Mathematical explanation

Regular languages via expressions

A language is regular if some regular expression denotes it. Equivalent definitions (proved later): accepted by a DFA; accepted by an NFA; generated by a right-linear (Type-3) grammar.

Finite languages are regular: $\{w_1,\ldots,w_m\} = L(w_1 + \cdots + w_m)$ (each $w_i$ written as a concatenation of symbols). $\Sigma^*$ itself is $L((a_1+\cdots+a_k)^*)$ when $\Sigma = \{a_1,\ldots,a_k\}$ .

Why star is the only iteration needed

Concatenation and union alone generate only finite languages. Star adds unbounded repetition, which is exactly what finite-memory machines can count in unary patterns such as $a^*$ , but not what they need for $a^n b^n$ .

Worked examples

Example 1: membership in $a^* b^*$

$L(a^* b^*) = \{ a^i b^j \mid i,j \ge 0 \}$ .

String	In the language?	Reason
$\varepsilon$	yes	$i=j=0$
`aaa`	yes	$i=3,j=0$
`bb`	yes	$i=0,j=2$
`aaabb`	yes	$i=3,j=2$
`ba`	no	a $b$ appears before an $a$
`aba`	no	an $a$ after a $b$

Example 2: $a + b^$ versus $(a+b)^$

$L(a+b^*) = \{a\} \cup \{ b^k \mid k \ge 0 \} = \{a, \varepsilon, b, bb, bbb, \ldots\}$ .
Strings not in it include ab, ba, aa.
$L((a+b)^*) = \{a,b\}^*$ , every string.

So ab distinguishes them.

Example 3: simplify $(a^* b^)^ (b^* a^)^$

Both $(a^* b^*)^*$ and $(b^* a^*)^*$ equal $\{a,b\}^*$ (any string can be split into blocks of $a$ 's followed by $b$ 's, or vice versa). Their concatenation is still $\{a,b\}^*$ . A simplified expression is $(a+b)^*$ .

Example 4: language of strings ending with `01`

One expression: $(0+1)^* 01$ .

Check: 01 matches ( $\varepsilon$ then 01); 101 matches; 0 does not; 010 does not (ends with 10).

A structurally different correct expression is $(1^* 0 0^* 1)(1^* 0 0^* 1)^*$ : cut the string just after each occurrence of 01; every block is some 1s, then at least one 0, then a 1. Proving two expressions equal this way (a decomposition argument) is an alternative to building automata.

Example 5: $\emptyset$ and $\varepsilon$ traps

$L(a + \emptyset) = L(a) = \{a\}$ .
$L(a \emptyset) = \emptyset$ .
$L(\emptyset^*) = \{\varepsilon\}$ .
$L((\emptyset + a)^*) = a^*$ .

Important properties and observations

Precedence: $*$ before concatenation before $+$ .
Regular expressions denote regular languages; not every language has an RE (for example $\{a^n b^n \mid n \ge 0\}$ ).
Many different REs denote the same language; minimization is for DFAs, not for REs.
$L(r^*)$ always contains $\varepsilon$ .
If $L(r) = \emptyset$ , then $L(r^*) = \{\varepsilon\}$ and $L(r s) = \emptyset$ .

Common misconceptions.

Reading $a+b^*$ as $(a+b)^*$ .
Thinking every infinite language needs an RE with star nested two deep; one star often suffices.
Claiming $r + s = s + r$ fails; union is commutative.
Claiming $rs = sr$ always; concatenation is not commutative.

GATE examination perspective

PRECEDENCE TRAPS. Expand $a+bc^*$ carefully before comparing languages.
WHICH STRINGS MATCH. Prefer converting a short RE to an NFA/DFA when membership of many strings is asked.
EQUIVALENCE OF TWO RES. Convert both to minimal DFAs and compare, or argue by identities. Do not rely on looking similar.
DESCRIBE THE LANGUAGE IN WORDS. Translate $(0+1)^* 1 (0+1)^*$ as "strings containing at least one 1".
LEXICAL REs. Token patterns in compilers are regular expressions; longest-match and priority rules are compiler issues, not pure language equality.
ONE COUNTEREXAMPLE KILLS AN IDENTITY. For a false claim, find the shortest string in one side and not the other; test $\varepsilon$ , single symbols, then ab and ba.
$\emptyset$ VERSUS $\varepsilon$ . $\emptyset^* = \varepsilon$ but $r \emptyset = \emptyset$ ; $\varepsilon$ is the identity for concatenation, $\emptyset$ for union.
"AT LEAST" AND "AT MOST". "At least one $a$ " is $(a+b)^* a (a+b)^*$ ; "at most one" is $b^*(\varepsilon + a)b^*$ . Check which one the wording asks for.

Summary

REs: $\emptyset$ , $\varepsilon$ , symbols, union $+$ , concatenation, star $*$ .
Precedence: star, then concat, then union.
$L(r)$ is always a regular language; finite languages and $\Sigma^*$ are regular.
Identities: annihilators, $\emptyset^* = \varepsilon$ , star absorption, distributivity.
Membership follows the inductive definition or an equivalent automaton.
Neither $(rs)^*=r^*s^*$ nor $(r+s)^*=r^*+s^*$ holds in general (see the distinct-symbol counterexamples); $(r+s)^* = (r^* s^*)^*$ and $r(sr)^* = (rs)^* r$ hold.
Check a proposed expression by counting short strings or by testing $\varepsilon$ , a, b, ab, ba.

Alphabets, Strings and Languages: prerequisite.
Equivalence of Regular Expressions and Finite Automata: dependent. Thompson construction and state elimination.
Lexical Analysis: related. REs as token patterns.

Regular Expressions

Introduction

Prerequisites

Core concepts

Inductive definition

Precedence and associativity

Shorthand

How it works

Evaluating membership

Algebraic identities

Equivalence traps

Writing expressions for standard languages

Algorithms and pseudocode

Mathematical explanation

Regular languages via expressions

Why star is the only iteration needed

Worked examples

Example 1: membership in $a^* b^*$

Example 2: $a + b^$ versus $(a+b)^$

Example 3: simplify $(a^* b^)^ (b^* a^)^$

Example 4: language of strings ending with `01`

Example 5: $\emptyset$ and $\varepsilon$ traps

Important properties and observations

GATE examination perspective

Summary

Sources

Next steps

Introduction

Prerequisites

Core concepts

Inductive definition

Precedence and associativity

Shorthand

How it works

Evaluating membership

Algebraic identities

Equivalence traps

Writing expressions for standard languages

Algorithms and pseudocode

Mathematical explanation

Regular languages via expressions

Why star is the only iteration needed

Worked examples

Example 1: membership in a∗b∗a^* b^*a∗b∗

Example 2: a+b∗a + b^*a+b∗ versus (a+b)∗(a+b)^*(a+b)∗

Example 3: simplify (a∗b∗)∗(b∗a∗)∗(a^* b^*)^* (b^* a^*)^*(a∗b∗)∗(b∗a∗)∗

Example 4: language of strings ending with 01

Example 5: ∅\emptyset∅ and ε\varepsilonε traps

Important properties and observations

GATE examination perspective

Summary

Related topics

Sources

Next steps

Example 1: membership in $a^* b^*$

Example 2: $a + b^$ versus $(a+b)^$

Example 3: simplify $(a^* b^)^ (b^* a^)^$

Example 4: language of strings ending with `01`

Example 5: $\emptyset$ and $\varepsilon$ traps