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:
aORb
So the language is:\[ L(a+b)=\{a,b\} \]
2. Concatenation
It means joining strings.\[ ab \]
means:
afollowed byb
So:\[ L(ab)=\{ab\} \]
Another example:\[ (a+b)c \]
produces:
acbc
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
- Kleene Star
* - Concatenation
- 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:
101111011001
All end in 1.
6. Example: Strings Starting with 1
Regular expression:\[ \boxed{1(0+1)^*} \]
Examples:
110111011100
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:
aabbababbbbabb
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
| Operator | Meaning | Example |
|---|---|---|
+ or | | OR / Union | a+b |
| Concatenation | Followed by | ab |
* | Zero or more | a* |
+ as repetition | One or more | a+ |
ε | 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
aorb.Concatenation:\[ ab \]
represents
afollowed byb.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} \]
