Skip to content
Home » Regular Expressions

Regular Expressions

1. Definition

A Regular Expression (RE) is a notation used to describe a Regular Language.

In simple words:

A Regular Expression is a pattern used to represent a set of strings.

It is widely used in Theory of Computation, pattern matching, lexical analysis, search tools, and compilers.


2. Basic Symbols of Regular Expression

The three most important operators are:

1. Union — + or |

It means OR.\[ a+b \]

means:

a OR b

So the language is:\[ L(a+b)=\{a,b\} \]


2. Concatenation

It means joining strings.\[ ab \]

means:

a followed by b

So:\[ L(ab)=\{ab\} \]

Another example:\[ (a+b)c \]

produces:

  • ac
  • bc

3. Kleene Star — *

It means zero or more repetitions.\[ a^* \]

means:\[ \{\epsilon,a,aa,aaa,aaaa,\ldots\} \]

Important:

* includes zero occurrences.


3. Some Common Examples

Example 1

\[ a^* \]

Strings:\[ \epsilon,a,aa,aaa,\ldots \]


Example 2

\[ a^+ \]

Means one or more as:\[ a,aa,aaa,aaaa,\ldots \]

Difference:\[ a^* = 0\text{ or more} \]\[ a^+ = 1\text{ or more} \]


Example 3

\[ (a+b)^* \]

This represents all possible strings made from a and b, including ε.

Examples:

  • ε
  • a
  • b
  • aa
  • ab
  • ba
  • bb
  • aab
  • abb
  • baba

4. Precedence of Operators

When multiple operators are used, remember this order:

Highest → Lowest

  1. Kleene Star *
  2. Concatenation
  3. Union + / |

For example:\[ a+bc^* \]

means:\[ a+(b(c^*)) \]


5. Example: Strings Ending in 1

Suppose:\[ \Sigma=\{0,1\} \]

We want all strings ending in 1.

The regular expression is:\[ \boxed{(0+1)^*1} \]

Examples:

  • 1
  • 01
  • 11
  • 101
  • 1001

All end in 1.


6. Example: Strings Starting with 1

Regular expression:\[ \boxed{1(0+1)^*} \]

Examples:

  • 1
  • 10
  • 11
  • 101
  • 1100

7. Example: Exactly One a

A regular expression for strings containing exactly one a, with b’s before and after it:\[ \boxed{b^*ab^*} \]

Examples:

  • a
  • ab
  • ba
  • babb
  • bbabb

8. Relationship with Automata

A very important concept:\[ \boxed{\text{Regular Expression} \equiv \text{Finite Automaton}} \]

A regular expression can be converted into an equivalent finite automaton, and a finite automaton can be represented by a regular expression.

Therefore:\[ \boxed{RE \leftrightarrow DFA \leftrightarrow NDFA} \]

All represent Regular Languages.


⭐ Important Operators for Exam

OperatorMeaningExample
+ or |OR / Uniona+b
ConcatenationFollowed byab
*Zero or morea*
+ as repetitionOne or morea+
εEmpty stringε

Note: In formal TOC notation, + commonly means union, while a+ is often used informally for one-or-more repetitions. Follow the notation used by your textbook/teacher.


⭐ Exam Answer — 5–10 Marks

A Regular Expression (RE) is a formal notation used to represent or describe a regular language. It defines a pattern for a set of strings over an alphabet.

The basic operations of regular expressions are union, concatenation and Kleene star.

Union:\[ a+b \]

represents either a or b.

Concatenation:\[ ab \]

represents a followed by b.

Kleene Star:\[ a^* \]

represents zero or more occurrences of a, including ε.

For example, the regular expression:\[ (0+1)^*1 \]

represents all binary strings ending in 1.

Regular expressions are equivalent to finite automata. Thus, regular expressions, DFA and NDFA represent the same class of languages, called regular languages.

🧠 Fast memory trick

RE has 3 main operations:

OR → +

JOIN → concatenation

REPEAT → *

And remember:\[ \boxed{RE \leftrightarrow DFA \leftrightarrow NDFA \leftrightarrow Regular\ Language} \]