Regular Language
A Regular Language is a formal language that can be expressed using regular
expressions and recognized by a finite automaton (DFA or NFA).
A language L is called regular if there exists a finite automaton (deterministic or
nondeterministic) that accepts all strings in L and rejects all strings not in L.
𝐿 is regular ⟺ ∃ a finite automaton 𝑀 such that 𝐿 = 𝐿(𝑀)
for example,
a*→ Strings like "", a, aa, aaa, ...
Alphabet and Strings
• Alphabet (Σ): A finite set of symbols (e.g., Σ = {0,1}).
• String: A sequence of symbols from the alphabet (e.g., 0101).
• Language (L): A set of strings over Σ.
These can be represented by regular expressions:
• (a)*
• (0*1*)
• (0+1)*1
Properties of Regular Languages:
• Closed under:
▪ Union ( 𝐿1 ∪ 𝐿2)
▪ Concatenation ( 𝐿1. 𝐿2)
▪ Kleene Star ( 𝐿∗ )
▪ Intersection, Complement, Difference, Reversal
Non – Regular Language Example
L = {[Link] n>= 0}
In the above language the number of a`s and number of b`s should be same which
is equal to n. But in case of finite automata the language can use (*) means 0 or
more repetitions or (+) which means one or more repetitions.
A regular language can be recognized by a finite automaton, which has limited
memory. But in 𝑎𝑛 𝑏 𝑛 , the machine must “remember how many a’s it has seen” so it
can check if the same number of b’s appear afterward. A finite automaton cannot
count an arbitrary number of a’s, so it cannot recognize this language.
Regular Expressions in Finite Automata
1. Introduction
A Regular Expression (RE) is a formal way to describe a set of strings (language) over a
given alphabet.
In the context of Finite Automata (FA), regular expressions are used to represent
regular languages — i.e., the same class of languages that can be recognized by
Deterministic (DFA) and Nondeterministic Finite Automata (NFA).
In short:
Regular Expression ⇄ Finite Automaton ⇄ Regular Language
2. Alphabet and Strings
• Alphabet (Σ): A finite set of symbols (e.g., Σ = {0,1}).
• String: A sequence of symbols from the alphabet (e.g., 0101).
• Language (L): A set of strings over Σ.
3. Basic Regular Expressions and Their Meanings
Expression Meaning Language Example (Σ = {0,1})
ϕ Empty set {}
ε Empty string {ε}
a Symbol ‘a’ {a}
R₁ + R₂ Union (OR) L(R₁) ∪ L(R₂)
R₁R₂ Concatenation {xy
R* Kleene Star Zero or more occurrences of L(R)
R⁺ One or more occurrences of L(R) R⁺ = RR*
4. Examples
Regular Expression Language Description
0* All strings of 0s (including ε)
1⁺ All strings of 1s (at least one 1)
(0+1)* All strings over {0,1}
0(0+1)* All strings starting with 0
(0+1)*1 All strings ending with 1
1(01)* Strings starting with 1 followed by any
number of “01”
Thompson’s Construction Rules
Each regular expression component has a corresponding NFA fragment.
Expression NFA Fragment Description
ε Start →ε→ Accept
a Start —a→ Accept
R₁ + R₂ ε-transitions split to R₁ and R₂ NFAs, then rejoin with ε
R₁R₂ Connect accept state of R₁ NFA to start of R₂ NFA using ε
R* New start and accept; loop back from accept to start with ε (for
repetition)
→a
1. RE → a
a
1 2
2. RE → a + b
a
1 2
3. RE → a . b
a b
1 2 3
4. RE → a *
a
5. RE → a+
a
1 2
Example: Convert RE = a(b + c)* into finite automata
Step-by-Step:
1. NFA for a.
a
1 2
2. NFA for (b + c) using union.
a
1 2
3 4
c
3. Apply Kleene star (*) to (b + c).
a
1 2
3 4
4. Concatenate a with (b + c)* using ε.
a
1 2
e
b
3 4
e
Practice questions:
1. Convert the regular expression R = a + b into a finite automaton.
2. Construct a finite automaton for R = ab.
3. Design a finite automaton for R = a*.
4. Convert the regular expression R = (a + b)* into its equivalent finite
automaton.
5. Build a finite automaton corresponding to the regular expression R = a(b +
a).
6. Convert the regular expression R = (a + b)*a(b + a) into a finite automaton.
7. Construct a finite automaton for the regular expression R = a(b + c)*b.
8. Design a finite automaton that accepts the language represented by R = (0
+ 1)*01(0 + 1)*.
9. Convert the regular expression R = (a + b)*abb into its equivalent finite
automaton.
10. Construct a finite automaton for R = (a + b)*bb(a + b)*.
11. Build a finite automaton corresponding to the regular expression R = (a +
b)a(a + b)*.
12. Convert the regular expression R = (0 + 1)*(00 + 11)(0 + 1)* into an
equivalent automaton.
13. Construct a finite automaton for the regular expression R = a*(ba)*.
14. Design a finite automaton equivalent to R = (a + b)*a(a + b)*a(a + b)*.
15. Convert the regular expression R = (a + b)*(ab + ba)(a + b)* into a finite
automaton.