10
Regular and Nonregular
Languages
25410.1INTRODUCTION
From exploring the knowledge of the previous chapters, for checking the regularity of any
language, we might say that, a language is said to be regular language if there exist a Finite
Automaton (FA) that accept it. In other words, a machine with finite number of states (DFA/
NFA/NFA with ε-moves) including definite halting state and no other means of storage,
recognizes the language that language is a regular language; otherwise language is not regular.
To prove any language is regular or not we discuss a theorem called pumping lemma for
regular language in the next section. Through pumping lemma we necessarily check the
regularity of any language. Section 10.2 and 10.3 discuses more about regularity and
nonregularity of any languages.
There are some inherent characterizations, if the language recognize as the regular
language. Closure characterization is one of them. Closure characteristics tell about the nature
of regular languages over operators. In section 10.4 we will see the nature of regular languages
over operations like union, concatenation, intersection and kleeny closure that also return a
regular language.
The problem of equivalence of regular languages can be a general one. Whether two
regular languages are equivalent, alternatively we have two DFAs corresponding to two different
regular languages, then whether these DFAs are equivalent. The solution of above problem is
finding out by the construction of a minimum state DFA that recognizes both the languages.
We discuss the problem of minimization of DFA with some other problems of regularity under
topic “Decision problems” in section 10.5 in details.
10.2PUMPING LEMMA FOR REGULAR LANGUAGE
Lemma 10.1. If L is a regular language then there exist a constant n such that if a string Z ∈
L and
| Z | = n, then Z can be written as,
Z = u.v.w
where, 1. |v| ≥ 1- |u.v| ≤ n
- ∀i ≥ 0, u.vi.w ∈ L
(where n depends only on language)
The statement of the pumping lemma says if we select any string Z from the set of
regular language L, such that string Z can be break into substrings u followed by substring v