2.12 EQUIVALENCE OF TWO AUTOMATAS


2.11 PROPERTIES OF REGULAR SETS

Since the union of two regular sets is always a regular set, regular sets are closed under the union operation. Similarly, regular sets are closed under concatenation and closure operations, because the concatenation of a regular sets is also a regular set, and the closure of a regular set is also a regular set.

Regular sets are also closed under the complement operation, because if L ( M ) is a language accepted by a finite automata M , then the complement of L ( M ) is & pound ; * ˆ’ L ( M ). If we make all final states of M nonfinal, and we make all nonfinal states of M final, then the automata accepts * ˆ’ L ( M ); hence, we conclude that the complement of L ( M ) is also a regular set. For example, consider the transition diagram in Figure 2.31.

click to expand
Figure 2.31: Transition diagram.

The transition diagram of the complement to the automata shown in Figure 2.31 is shown in Figure 2.32.

click to expand
Figure 2.32: Complement to transition diagram in Figure 2.31.

Since the regular sets are closed under complement as well as union operations, they are closed under intersection operations also, because intersection can be expressed in terms of both union and complement operations, as shown below:

where L 1 denotes the complement of L 1 .

An automata for accepting L 1 ˆ L 2 is required in order to simulate the moves of an automata that accepts L 1 as well as the moves of an automata that accepts L 2 on the input string x . Hence, every state of the automata that accepts L 1 ˆ L 2 will be an ordered pair [ p , q ], where p is a state of the automata accepting L 1 and q is a state of the automata accepting L 2 .

Therefore, if M 1 = ( Q 1 , , 1 , q 1 , F 1 ) is an automata accepting L 1 , and if M 2 = ( Q 2 , , 2 , q 2 , F 2 ) is an automata accepting L 2 , then the automata accepting L 1 ˆ L 2 will be: M = ( Q 1 Q 2 , , , [ q 1 , q 2 ], F 1 F 2 ) where ([ p , q ], a ) = [ 1 ( p , a ), 2 ( q , a )]. But all the members of Q 1 Q 2 may not necessarily represent reachable states of M . Hence, to reduce the amount of work, we start with a pair [ q 1 , q 2 ] and find transitions on every member of from [ q 1 , q 2 ]. If some transitions go to a new pair, then we only generate that pair, because it will then represent a reachable state of M .

We next consider the newly generated pairs to find out the transitions from them. We continue this until no new pairs can be generated.

Let M 1 = ( Q 1 , , 1 , q 1 , F 1 ) be a automata accepting L 1 , and let M 2 = ( Q 2 , , 2 , q 2 , F 2 ) be a automata accepting L 2 . M = ( Q , , , q , F ) will be an automata accepting L 1 ˆ L 2 .

 begin  Q   old  =    Q   new  = { [  q   1  ,  q   2  ] }         While (  Q   old     Q   new  )         {               Temp =  Q   new     Q   old   Q   old  =  Q   new  for every pair [  p  ,  q  ] in Temp do                        for every a in   do  Q   new  =  Q   new      ([  p  ,  q  ],  a  )         }  Q  =  Q   new  end 

Consider the automatas and their transition diagrams shown in Figure 2.33 and Figure 2.34.

click to expand
Figure 2.33: Transition diagram of automata M 1 .
click to expand
Figure 2.34: Transition diagram of automata M 2 .

The transition table for the automata accepting L ( M 1 ) ˆ L ( M 2 ) is:

A

b

[1, 1]

[1, 1]

[2, 4]

[2, 4]

[3, 3]

[4, 2]

[3, 3]

[2, 2]

[1, 1]

[4, 2]

[1, 1]

[2, 4]

[2, 2]

[3, 1]

[4, 4]

[3, 1]

[2, 1]

[1, 4]

[4, 4]

[1, 3]

[2, 2]

[2, 1]

[3, 1]

[4, 4]

[1, 4]*

[1, 3]

[2, 2]

[1, 3]

[1, 2]

[2, 1]

[1, 2]*

[1, 1]

[2, 4]

We associate the names with states of the automata obtained, as shown below:

[1, 1]

A

[2, 4]

B

[3, 3]

C

[4, 2]

D

[2, 2]

E

[3, 1]

F

[4, 4]

G

[2, 1]

H

[1, 4]

I

[1, 3]

J

[1, 2]

K

The transition table of the automata using the names associated above is:

a

B

A

A

B

B

C

D

C

E

A

D

A

B

E

F

G

F

H

I

G

J

E

H

F

G

I *

J

E

J

K

H

K *

A

B




Algorithms for Compiler Design
Algorithms for Compiler Design (Electrical and Computer Engineering Series)
ISBN: 1584501006
EAN: 2147483647
Year: 2005
Pages: 108
Authors: O G Kakde

flylib.com © 2008-2017.
If you may any questions please contact us: flylib@qtcs.net