Regular Languages and their Properties
Prof. (Dr.) K.R. Chowdhary
Former Professor & Head, Department of Computer Sc. & Engineering
MBM Engineering College, Jodhpur

kr chowdhary

TOC

1/ 14

K.R. Chowdhary

Theory of Computation
Automata, Formal Languages, Computation and Complexity
Focuses on pedagogy in its writing, that represents a refreshing
approach
Ensures comprehensive and enjoyable learning
Undergone a rigorous classroom testing

©2025

Get 20% off with this code: SPRAUT
Available on Springer Nature Link
Please note that promotional coupons are only valid for English-language Springer, Apress, and Palgrave Macmillan books
& eBooks and are redeemable on link.springer.com only. Titles affected by fixed book price laws, forthcoming titles and
titles temporarily not available on Springer Nature Link are excluded from promotions, as are reference works, handbooks,
encyclopedias, subscriptions, or bulk purchases. The currency in which your order will be invoiced depends on the billing
address associated with the payment method used, not necessarily your home currency. Regional VAT/tax may apply.
Promotional prices may change due to exchange rates. Promotions are valid for individual customers only. Booksellers,
book distributors, and institutions such as libraries and corporations please visit springernature.com/contact-us.
Promotions do not work in combination with other discounts or gift cards.

link.springer.com/book/
9789819762347

Introduction to Regular languages

There is a cycle: for regular expression there is corresponding regular
language, for reg. language there is a corresponding NFA, for NFA
there is a corresponding DFA, and for that there is a corresponding
regex. It indicates that all these have same capabilities.
We know that regular expressions are closed on ∪, ◦, and ∗. Do
these properties also apply to Reg, languages?

kr chowdhary

TOC

2/ 14

Regular languages are closed on ∪, ◦, and ∗
The approach for this is: If after performing these operations on reg.
languages, if they are still accepted by FA, then they (reg. languages) are
closed. This is because, the FA recognize regular languages. Thus, the
proof reduces only to: find corresponding FA for these closure
properties.
Theorem
Regular languages are closed on Union.
Proof.
Assume that M1 = (Q1 , Σ1 , δ1 , s1 , F1 ) and M2 = (Q2 , Σ2 , δ2 , s2 , F2 ) are two
FA recognizing the regular languages L1 = L(M1 ) and L2 = L(M2 ). Let
L(M) = L(M1 ) ∪ L(M2 ) is the language recognized by a union automaton,
such that, L(M) = {w |w = x ∪ y , x ∈ L1 , y ∈ L2 }. That is, M accepts w
iff M1 accepts x or M2 accepts y .

kr chowdhary

TOC

3/ 14

Regular languages Theorem
Proof.
Closed on Union: Let the automata M which accepts L1 ∪ L2 is as
shown below.

If w = x, the FA M non-deterministically decides a ε-transition from new
state s to s1 , and then there are transitions in M1 , and when f1 ∈ F1 is
encountered there is a ε−transition from f1 to f . Similar phenomena
occurs for M2 when w = y .
The resultant FA M = (Q, Σ, δ , s, F ) is given as: Q = Q1 ∪ Q2 ∪ {s, f },
Σ = Σ1 ∪ Σ2 ∪ {ε}, start state=s, final state=f , and δ is given in next
slide.
kr chowdhary

TOC

4/ 14

Regular languages theorem
Proof.
Closed on Union contd.: The δ
δ (q, a) = δ1 (q, a), if q ∈ Q1 and a ∈ Σ1
δ (q, a) = δ2 (q, a), if q ∈ Q2 and a ∈ Σ2
δ (q, a) = {s1 , s2 }, if a = ε and q = s
δ (q, a) = δ (q, a) = f , if q ∈ F1 ∪ F2 and a ∈ ε

hence
L = L(M) = {x ∪ y | x ∈ Σ∗1 , and y ∈ Σ∗2 }.

kr chowdhary

TOC

5/ 14

Regular languages theorem
Theorem
Regular languages are closed on the operation of concatenation.

Proof.
Let L = L(M1 ) ◦ L(M2 ) = {w = x ◦ y | x ∈ L(M1 ), y ∈ L(M2 )}. Here, M1
recognizes x and reaches to its final state, then there is a ε-transition
from f1 ∈ F1 to s2 , then M2 recognizes y . M is defined in terms of M1
and M2 as: Q = Q1 ∪ Q2 , Σ = Σ1 ∪ Σ2 ∪ {ε}, s = s1 , f = f2 and δ is:
δ (q, a) = δ1 (q, a), q ∈ Q1 , a ∈ Σ1 , δ (q, a) = {s2 }, q ∈ F1 , a = ε
δ (q, a) = δ2 (q, a), q ∈ Q2 , a ∈ Σ2 .
kr chowdhary

TOC

6/ 14

Regular languages theorem
Theorem
Regular languages are closed on the operation of kleene-star.

Proof.
This is extension of concatenation,
i.e., the input x ∈ L(M1 ) is pumped
zero or more number of times.
L = L(M) = (L(M1 )∗ ) = L∗1 = {w =
x ∗ | x ∈ L1 }. The formal definition
of M = (Q, Σ, δ , s, F ) is:
Q = Q1 ∪ {s, f }, Σ = Σ1 ∪ {ε}, start
state=s, final state=f , and δ is:
kr chowdhary

δ (q, a) = {s1 , f }, if q = s, a = ε,
δ (q, a) = δ1 (q, a), if q ∈ Q1 , a ∈ Σ1 ,
δ (q, a) = {s1 ∪ f }, if q ∈ Q1 , a = ε

This proves the theorem.
TOC

7/ 14

Construction of FA for a given Regex
Example
Given the regex r = (ab + aba)∗ , we can find the FA as follows:
Systematically apply the theorem discussed above to construct the FA
using elementary steps. 1. Construct the NFA for regex r1 = ab, 2.
Construct NFA for r2 = aba, 3. Construct NFA for r3 = r1 + r2 = ab + aba,
4. Finally, construct NFA for r3∗ = (r1 + r2 )∗ = (ab + aba)∗

kr chowdhary

TOC

8/ 14

FA to Regex: State removal method
Lemma
A language is regular then it can be described by a regex.
Proof.
1

Because L is regular, it can be represented by a DFA.

2

Convert the DFA into equivalent regex.

3

First convert DFA into GNFA (Generalized NFA) then convert GNFA
into regex. This proves the lemma.

Definition
(GNFA.) A GNFA G reads blocks of symbols rather than single symbol at
a time, has single start state and single final state. If GNFA is
G = (Q, Σ, ρ, q0 , qf ), then ρ : Q − {q0 } × Q − {qf } → RΣ , RΣ is set of all
regular expressions over alphabet Σ.

kr chowdhary

TOC

9/ 14

FA to Regex: State removal method

1

DFA-to-GNFA:
add new start state (qstart ) with ε−transition to original start state
q0

2

add new end state with ε−transition from each of the original final
state.

3

If original transition arrow has multiple labels, we replace these with
a new arrow whose label is regular expression formed by the union of
the labels.

4

we iteratively remove one state in GNFA, such that new GNFA
obtained will recognize the same language.

5

When number of states in GNFA are two, we have obtained the
regex for the given DFA.

kr chowdhary

TOC

10/ 14

FA to Regex: State removal method

Example
The diagram below shows state removal and gives regex for a FA.

kr chowdhary

TOC

11/ 14

FA to Regex Brozozowski’s method
This method generates regex by
generating sequence of symbols (or
equivalently, scanning the sequence
of symbols). Suppose we want to
find the regular expression for the
FA given below.

q = 0q + (1p + ε); ε symbols
indicates that when input is
accepted, no transition is
required. So,
q = 0∗ (1p + ε); by Arden’s
theorem: X = X 1 + Y = X ∗ Y ,
so
q = 0∗ 1p + 0∗ (ε)
= 0∗ 1p + 0∗
p = 0p + 1q

Starting from each state we we
write a equation showing the
generating of sequence of state and
edge labels. Finally, after doing
substitutions, we keep the equation
of start state, without any
variables(i.e., other state symbols).
p = 0p + 1q
kr chowdhary

= 0p + 1(0∗ 1p + 0∗ )
= 0p + 10∗ 1p + 10∗
= (0 + 10∗ 1)∗ (10∗ ); by Arden’s
rule.
Hence, the required regex is
(0 + 10∗ 1)∗ (10∗ ).
TOC

12/ 14

Kleene’s theorem
Theorem
A language is regular iff it is accepted by FA.
Proof.
The proof has two parts: 1. If the
language is regular then it is
accepted by FA, and 2. If a
language is accepted by FA then it
is regular.
Part 1: By definition of regularity,
following are regular:
φ , {a1 , a2 , . . . , an }, {ai } ∪ {aj }, {ai } ◦
{aj }, ai∗ . The diagrams shown
below are of FA recognizing the
first two.
We have already proved that FA
exists for the following regular
languages:
kr chowdhary

{ai } ∪ {aj }, {ai } ◦ {aj }, ai∗ .

Part 2: Using the method of state
reduction (converting to GNFA)
and Brozozowki methods we have
proved that there exists regex for
every FA. Hence, the complete
proof.
TOC

13/ 14

Bibliography

Chowdhary, K.R. (2025). Regular Languages. In: Theory of
Computation. Springer, Singapore.
https://doi.org/10.1007/978-981-97-6234-7_5

kr chowdhary

TOC

14/ 14

