Mathematical Foundation of Computer Science

DHARM

228 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE

Consideration of paths are shown in Fig. 9.12, where following possibilities of paths
exist,

1. There are few paths where, intermediate states are always < k, or states of upto (k – 1)
   will be consider hence the expression for this path will be iRjK–1.


2. There are few paths where, intermediate states are always > k, so skip those paths.


3. A path from qi to qj can be divided into qi to qk and then qk to qj, i.e.,
   In the path qi to qk where all intermediate sates are ≤ (k – 1) so, expression is iRkK–1,
   followed by
   l The path where on state k, few transitions are return back to state k itself by
   passing through all intermediate states ≤ (k – 1) so, expression is (kRkK–1), followed
   by,
   l The path qk to qj where all-intermediate states ≤ (k – 1) so, expression is kRjK–1.
   Thus, the combination of above possibilities we obtain the following expression,
   iRj
   K =
   iRj
   K–1 ∪
   iRk
   K–1. (
   kRk
   K–1).
   kRj
   K–1.
   or, iRjK = iRjK–1 + iRkK–1. (kRkK–1)*. kRjK–1.
   Therefore, we could also find the expression for any k = n i.e., iRjn.
   Since, expression R expresses the language of DFA M so each R is associated with the
   regular expression i.e.,

irj
K =
irj
K–1 +
irk
K–1. (
krk
K–1).
krj
K–1.
Assume DFA M starts from state 1 and set of final states are {f 1 , f 2 , ......fp} then,
L(M) = { 1 Rf1n ∪ 1 Rf2n .......... ∪∪∪∪∪ 1 Rfpn}
So the language set contains the union of the languages consists of each path from state
1 to each state of F (final state).
Then regular expression r = 1 rf1n + 1 rf2n + ...... + 1 rfpn
Hence, the proof of the theorem is ended.
General rules for simplification of regular expressions
l (∈ + r ) = r
∴ L[(∈ + r)] = ∈ + L(∈ + r)+ L(∈ + r) L(∈ + r) + ......
= ∈ + L(r ) + L(r)L(r ) + ......
= L( r )
l (∈ + r) r = r .r = r+
l (∈ + r).r = r + r r = r
∴ L(r r) = L(r) .L(r) = L(r). {∈ + L(r) + L(r).L(r) + ......}
= L(r) + L(r). L(r) + ......
and L(r) = ∈ + L(r) + L(r). L(r) + ......
so L(rr) + L(r) = ∈ + L(r) + L(r). L(r) + ......
= L( r)
l Φ + r = Φ
l Φ r = Φ
l (r)= r