Mathematical Foundation of Computer Science

DHARM

REGULAR AND NONREGULAR LANGUAGES 273

(iii)

A

B

D

E

F

G

C

0

1

1

1

1

1

1

1

1

0

0

0

0

0

0

(iv)

d e

a

c

b

f

0

0 0

0 0

0

1

1

1

1

1

(v) A B C

D

100

0 1

Î

Î

Î

1,Î

Fig. 10.16

10.4 Let L be a regular language then prove that ½(L) is also regular, where

½(L) = {x ∈ Σ*/x.y ∈ L for some y ∈ Σ* and |x| = | y|}

[Hint : Assume L = {0010, 01, 001110, 00, ......} then ½(L) = {00, 0, 001, 0, .......}. Let M be a DFA

which accepts L i.e., M = (Q, Σ, δ, q 0 , F) and the language ½(L) is accepted by the DFA M′ = (Q ×

Q × Q ∪ {q 0 ′}, Σ, δ′, q 0 ′, F′). Further, assume