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

kr chowdhary

TOC

1/ 10

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

Testing regularity - Intro

Consider language
L = {an b n |n ≥ 0}. While reading
from tape the FA has to remember
arbitrarily large number of a’s to
compare later with number of b’s.
Since, there is no arbitrary size
storage in FA, no FA can recognize
this language, hence L is not
regular.
Other proof: Since a string in L
can be arbitrarily large and states

kr chowdhary

are finite, some state will be
revisited (say qi = qj , i ̸= j) in the
process of recognition. Hence, for
some m ̸= n, there may be
δ ∗ (q0 , am ) = qi and δ ∗ (q0 , an ) = qi .

δ ∗ (q0 , am an ) = δ ∗ (δ ∗ (q0 , am ), b n )
= δ ∗ (qi , b n )
= qf .

TOC

2/ 10

Kleene star properties of Regular languages
Let M = (Q, Σ, δ , s, F ), |Q| = n, s = q0 , qm ∈ F , m ≥ n, and
w = a1 a2 . . . am . Since |w | > |Q|, some states are repeated due to
pigeonhole principle. Say, one state revisited is qi = qj for 0 ≤ i < j ≤ m.
Thus, the state sequence visited during the recognition is:
q0 . . . qi−1 qi , qi +1 . . . qj−1 qj , qj +1 . . . qm .

The string w is recognized through the path FA as follows:
δ ∗ (q0 , a1 a2 . . . am ) = δ ∗ (δ ∗ (q0 , a1 a2 . . . ai ), aj +1 aj +2 . . . am )
= δ ∗ (qi , aj +1 aj +2 . . . am )
= δ ∗ (qj , aj +1 aj +2 . . . am ) = qm ∈ F .
kr chowdhary

TOC

3/ 10

Kleene star properties of Regular languages...
Therefore a1 a2 . . . ai ai +1 . . . aj aj +1 . . . am ∈ L(M). Also,
a1 a2 . . . ai aj +1 . . . am ∈ L(M). Since, qi = qj , the substring ai +1 . . . aj−1 can
be repeated an arbitrary times (pumped), and still the string w will be
recognized, i.e.,
a1 a2 . . . ai (ai +1 . . . aj )k aj +1 . . . am ∈ L(M), for k ≥ 0
The above is specified in the form of a lemma, given below.
Lemma
(Pumping Lemma.) Given a FA M, |Q| = n, w ∈ L(M), |w | ≥ n, there
exists a decomposition of w as xyz, such that |xy | ≤ n, |y | ≥ 1, k ≥ 0, so
that there is always xy k z ∈ L(M).
Proof.
The proof has been discussed above using the diagram. If a language
string w fails to satisfy the criteria xy k z ∈ L(M), then it is not regular.
Note that pumping lemma apply to only infinite language, and it is for
negative, i.e., used to prove the non-regularity of a language, for that
some how we should have strategy to show that xy k z ∈
/ L(M).
kr chowdhary

TOC

4/ 10

Testing non-regularity
Example
Show that L = {an | n is prime} is non-regular.
Solution
Solution: let w = xy k z, k ≥ 0, x = ap , y = aq , z = ar , |q| ≥ 1. Therefore
w = ap (aq )k ar = ap+kq +r . Thus, we need to show that p + kq + r is not
prime. Let us assume that k = p + 2q + r + 2, we have;
p + kq + r = p + (p + 2q + r + 2)q + r
= p + pq + 2q 2 + rq + 2q + r
= 1(p + 2q + r ) + q(p + 2q + r )
= (p + 2q + r )(1 + q)
Since the string w = an can be factorized in pumping lemma, the
language is not regular.

kr chowdhary

TOC

5/ 10

Myhill-Nerode(MN) Theorem
The pumping lemma holds for some non-regular languages only, and does
not provide sufficient condition to prove that a language is regular. If
pumping lemma fails to prove non-regularity, it does not imply otherwise.
Theorem
(MN.) For x, y , z ∈ Σ∗ , a “distinguishing extension” z is such that xz ∈ F
but yz ∈
/ F . Therefore x ∼ y iff there is no distinguishing extension z.
The ∼ is equivalence relation which divides all w ∈ Σ∗ into equivalence
classes.
If x ∼ y , and there is xz ∼ yz, and x, y , z ∈ Σ∗ , then equivalence relation
is called right invariant. The x ∼L y is equivalence relation for language L
if xz ∈ L ⇔ yz ∈ L.
Definition
Index of a equivalence class is total number of equivalence classes in
the language. x ∼M y is equivalence relation for DFA M if same state is
reachable for inputs x, y ∈ Σ∗ .

kr chowdhary

TOC

6/ 10

Myhill-Nerode(MN) Theorem
Definition
(ver.2 MN theorem.) If ∃w ∈ Σ∗ for states p, q such that δ ∗ (p, w ) ∈ F ∧
/ F ), then w is distinguishing string for p, q. If there does not
δ ∗ (q, w ) ∈
exists any distinguishing string for p, q then they are not equivalent.
Theorem
MN theorem states that L is regular iff ∼L has finite index, and number
of states in the smallest DFA recognizing L is equal to index of the
equivalence class in ∼L .
Intuition of above is: if such a
minimal automaton is obtained,
then any two string x, y driving the
automaton into the same state, will
be in the same equivalence class.
I.e., the equivalence relation ∼L
creates partition set on the strings
kr chowdhary

Σ∗ , and size of partition set is
number of states in the FA.

TOC

7/ 10

MN Theorem: Example
Example
Consider a language on Σ = {a, b}, such that last but one character in w
is b.
Solution
The FA and equivalence classes are
shown below.

part after dot, i.e. ∗ba is
distinguishing extension z, such
that xz ∼ yz. Patterns in other
three equivalence classes are on the
same lines.

In the diagram below, the
substrings in “ε, a, . ∗ ba”: before
dot sign (ε, a) correspond to
equivalent strings x, y in
equivalence relation x ∼ y . The
kr chowdhary

TOC

8/ 10

MN Theorem: Examples

Example
Show that the language on L = {an b n |n ≥ 0} is non-regular.
Solution
Let S = {ε, a, aa, aaa, aaaa, . . . } is infinite over {a, b}. Let ak and am are
pair-wise distinguishable for k ̸= m.
Consider distinguishing extension z = b m . Appending z with pair-wise
distinguishing strings, we have ak b m ∈
/ L and am b m ∈ L. Therefore ak , am
are distinguishable w.r.t. L. Since k and m are taken arbitrary numbers,
there are arbitrarily large number of pair-wise distinguishing strings. This
corresponds to infinite states, hence the language is not regular.

kr chowdhary

TOC

9/ 10

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

10/ 10