Mathematical Foundation of Computer Science

DHARM

256 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE

Therefore string v can be pumped as many as you can such that the resulting string

{u.vi.w/∀i≥ 0 } will be accepted by DFA M. Hence language is a regular language.

Remember, above lemma checks the regularity of any language whose length is greater

then or equal to the number of states of its DFA. So, initially break the string into three

substrings and then test the effects of finite repetition of middle string on any of the interme-

diate state (not the final state) if it causes final string is in language then language is regular

otherwise language is nonregular.

10.3REGULAR AND NONREGULAR LANGUAGES SOLVED EXAMPLES

Now we test the regularity of any language using pumping lemma discussed above. This section
gives the idea that how to proceed to testify the language is a regular language using pumping
lemma. The examples discussed below presented the approach to reach the conclusion to the
problems.
Example 10.1. Let Σ = {0, 1}, then check the regularity of language L = {0k 1 k | k ≥ 0}.
Sol. The language L consists of following set of string {∈, 01, 0011, 000111, ...........}. We shall
prove the regularity of L by method of contradiction. Thus, assume L is regular and n is any
constant then string Z can be written as,
Z = 0n. 1n i.e., | Z | = 2n so | Z | > n
Now break the string Z into substrings u , v and w (Fig. 10.3) i.e.,
Z = 0n. 1n = u. v. w
where substrings fulfill the condition such that
(000............0 0......000). (111..................1111)
uv w

Fig. 10.3
We observe that string u.v consist only of 0’s so | u. v | ≤ n and | v | ≥ 1. For the
verification of the base case of pumping lemma i.e., string Z = u.vi.w ⇒ u.w (for i = 0).
Lemma says if L is regular then u.w ∈ L. Since substring u contains 0’s that are fewer than n
(because of few 0’s are part of substring v) and substring w contains exactly n, 1’s. So, string
u.w doesn’t have equal numbers of 0’s followed by equal number of 1’s. Hence, we obtain a
contradiction therefore L is not regular.

Example 10.2. If Σ = {0} and language defined over Σ is L = { 0 i^2 | i ≥ 0} then L is not regular.
Sol. Now, the strings in the set L = {∈, 0, 0000, 00000000, ......}.
Assume L is regular, then there exist a constant n s.t.
String Z =^0
n^2
(| Z | = n^2 ≥ n) and it can be broken into substrings u, v and w s.t.
Z = u. v. w and these substrings are:
(0........0 0........00). (0............00)...............................(0...................00)
uv w

(In the string Z there are n sets that contains n number of 0’s, so total n^2 0’s)

Since, v ≠ ∈ and | u. v | ≤ n ; means that sub string uv should be in first set that

contains n, 0’s. Substring u has less than n 0’s because some of 0’s are in v.