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

kr chowdhary

TOC

1/ 6

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

Regular Languages
The set R on an alphabet Σ is regular language, defined as follows:
φ ⊆ R, {ε} ⊆ R, {a} ⊆ R for all a ∈ Σ
if L1 , L2 ⊆ R, then L1 ∪ L2 ⊆ R, L1 ◦ L2 ⊆ R, and L∗1 ⊆ R.
The language {0, 00, 01, 000, 001, 010, 011, 0000, . . . }, which consists
all binary strings is regular. It can be constructed using regular
expression {0} ◦ ({0} ◦ {1})∗ .
A Regular language is represented by regular expression.
Definition
Following are regular expressions:
1
2

3

φ , ε, and a ∈ Σ are regular expressions.
if α, β are regular expressions, the α ∪ β , α ◦ β , and α ∗ are also regular
expressions.
Nothing else is regular expression.

A language is regular iff there is regular expression to represent it.
kr chowdhary

TOC

2/ 6

Regular Languages
Definition
Every regular expression has functional mapping to a regular language, as
follows:
The regular languages corresponding to regular expressions φ , ε are:
φ , and {ε}, respectively.
if α, β are reg. expressions, then corresponding regular languages
are: L {α}, and L {β }.
Also, L {α ◦ β } = L {α}L {β }, L {α ∪ β } = L {α} ∪ L {β },
L {α ∗ } = L {α}∗
If L is regular, then is L̄ also regular (to be seen in the study of finite
automata)
Is the intersection of two regular languages also necessarily regular?
(to be seen later)
Are all the languages regular? Justify(to be seen later)

kr chowdhary

TOC

3/ 6

Regular Languages
All the regular expressions can be listed of increasing length. Hence,
they can be mapped with set N.Thus regular expressions are
countable. However, set of all the possible languages on set Σ∗ is
∗
power set 2|Σ | , which is not countable. Conclusion: There are
not enough regular expressions to represent all languages.
Language over Σ = {a, b} for regex (a + b)∗ is: L = L ((a + b)∗ )
= {ε, a, b, aa, ab, ba, bb, aaa, . . . }, which is countably infinite set.
Thus, L is bijection to the set N. Thus, L is called Recursively
Enumerable language (RE).
Definition
(RE). A language L is RE if there exists an algorithm that, when given an
input w , eventually halts iff w ∈ L. Equivalently, there is an algorithm
that enumerates the members of L. If necessary, this algorithm may run
forever. Thus, L is called semidecidable language.

kr chowdhary

TOC

4/ 6

Regular Languages
Consider the language L = {a, ab, bba, bca, abcd}, which has bijection
with a set n ∈ N, such that |n| = |L|. The mapping of bijection is
{(0, a), (1, ab), (2, bba), (3, bca), (4, abcd)}. The language, L above is
called recursive.(R)
Definition
(Recursive). A language L is recursive if there exists an algorithm that,
given an input word w , will determine in a finite amount of time if w ∈ L
or not. A recursive language is decidable.
A recursive (R) language is enumerable. Hence, R ⊆ RE.
A set of programs that do not terminate on some inputs are not RE.
Since regular languages are countable, and for each countable set
there are uncountable subsets of languages. Thus, there exists
languages which are not regular.
Conclusion: All languages are not the regular languages.

kr chowdhary

TOC

5/ 6

Bibliography

Chowdhary, K.R. (2025). Finite Automata and Regular Expressions.
In: Theory of Computation. Springer, Singapore.
https://doi.org/10.1007/978-981-97-6234-7_2

kr chowdhary

TOC

6/ 6