Mathematical Foundation of Computer Science

DHARM

274 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE

x.y = a 1 a 2 ............... an. b 1. b 2 ................ .. bn

q 0 q 1 q 2 qn–1 qn qn+1 qn+2 q 2 n–1 q 2 n

(where q 2 n ∈ F)

So a state is the group of states p, q, and r i.e., {p, q, r} where state p is concern with the first part

of the string (i.e., x), state q is concern with the second part of the string (i.e., y), and state r is

concern to the nondeterministic guess i.e. state qn. Therefore δ′({p 1 , p 2 , p 3 }, a) = {δ(p 1 ,a), r, p 3 } if

and only if δ(p 2 , b) = r for some b ∈ Σ ; δ(q 0 ′, ∈) = {q 0 , q, q} s.t. for all q ∈ Q and F′ = {q, qf, q} s.t. for

all q ∈ Q and qf ∈ F.

Let Σ = {0} and L = {00}* = {∈, 00, 0000, ...........} then ½(L) = {∈, 0, 00, ........} = {0}*. Thus there

transitions diagram are shown in Fig. 10.17 (a) and (b) which are the FA’s hence ½(L) is also

regular].

0

0

q 0 q 1

()Ma

{,,}qqq 000 {,,}qqq 010

{,,}qqq 001

{,,}qqq 100

{,,}qqq 110

{,,}qqq 011 {,,}qqq 101 {,,}qqq 111

q 0 ¢

0

0

0

0

Î

Î

()Mb ¢

Fig. 10.17

10.5 Prove that L = {0m 1 n/gcd(m, n) = 1} is not regular.

[Hint : Assume Z = 0r 1 k = u.v.w where r + k ≥ n and gcd(r, k) = 1.

Let r = p 1. n! and k = r! + 1 where r ≥ n (1 ≤ |v| = n) and k is prime. Hence, test u.vi+1.w ∈ L. Since

u.vi+1 is the string of full of 0’s, i.e. number of 0’s are

r + i |v| = r + n! (k – p 1 ) |v|/|v| [because i = n! (k – p 1 )/|v|]

= r + n! (k – p 1 )

= n! p 1 + n! k – n! p 1

= n! k [number of 0’s]

Since number of 1’s are k hence gcd(r, k) ≠ 1.Hence, pumping lemma violated.

[Therefore L is not regular.]

10.6 Find an example of a nonregular language L ∈ {0, 1}* such that L^2 is regular.

10.7 Find an example of a language L ∈ {0, 1}* such that L* is not regular.

10.8 Let L 1 and L 2 are two languages over Σ then we define quotient of L 1 and L 2 to be the language

i.e.,

L 1 /L 2 = {x/for some y ∈ L 2 , x y ∈ L 1 }

Show that if L 1 is regular then L 1 /L 2 is also regular for any arbitrary language L 2.