Mathematical Foundation of Computer Science

DHARM

REGULAR AND NONREGULAR LANGUAGES 257

Remaining (n – 1) set of n number of 0’s are in w.
For the base case of pumping lemma, if u.w is in L then L is regular.
The strings u.w contains fewer than n 0’s , followed by (n – 1) set of n number of 0’s. So,
total numbers of 0’s in u.v are, where we assume u has k 0’s s.t. k < n.
So, 0k+(n–1).n is not a perfect square ⇒ u.w ∉ L
So, there is a contradiction. Hence language L is not regular.
Or, Assume Z = 0n^2 ≡ u. v. w ∈ L.
Check the string u.v^2 .w if this is in L then number are 0’s should be perfect square.
i.e. | u. v^2. w | = | u. v. w | + | v |
= n^2 + | v |
since | v | is least 1,
Hence, n^2 + | v | > n^2
Max length of substring | v | = n
So, n^2 < | u. v^2. w | < n^2 + n → to make perfect square add constant (n +1)
⇒ n^2 < | u. v^2. w | < n^2 + n + (n + 1)
⇒ n^2 < | u. v^2. w | < (n + 1)^2
i.e. the length of string ≠ (n + 1)^2 a perfect square ⇒ u. v^2. w ∉ L.
Hence, Language is not regular.
Example 10.3. If language L = {0i 1 j 2 i | i and j are arbitrary Integers} then L is not regular.
Sol. Language L contains the strings that have equal number of 0’s and 2’s, and in between 0’s
and 2’s it has any number of 1’s.
Assume a constant n (and a constant m where n > m), so that string Z = 0n 1 m 2 n;
If L is regular then, Z can be break into substring u , v and w s.t.
Z = 0n 1 m 2 n = u. v. w where u, v and w are given as follows:
(0............0 0..................0) (1......................1) (2......................2)
uv w

substring v ≠ ∈ ⇒ | v | ≥ 1 and | u. v | ≤ n

Proof by contradiction:
Assume L is regular so ∀ i ≥ 0, u. vi. w ∈ L.
For base case (i = 0) of pumping lemma, u. w ∈ L if L is regular.
Since, u. w has fewer than n 0’s (because some of 0’s are part of v) followed by m 1’s and
n 0’s.
From the nature of language L we find that only those strings are in L that have equal
number of 0’s (followed by any number of 1’s) and 2’s.
However, u. w doesn’t fulfill above condition. So, a contradiction,
Hence, u. w ∉ L.
For i = 2 , string Z = u. vi. w ⇒ u. v^2. w
So, | u. v^2. w | = | u. v. w | + | v |
⇒ = ( 2n + m) + | v | where 1 ≤ | v | ≤ n
⇒ (2n + m) + | v | > (2n + m)
i.e., (2n + m) < | u. v^2. w | < (2n + m) + n