OR Two Finite Automata FA3=FA1 OR FA1

 OR Two Finite Automata

Consider the following two FAs:

 

 

 

FA1 accepts all words with a double a in them.

FA2 accepts all words ending with b.

Let’s follow the algorithm to build FA3 that accepts the union of the two languages.

 

 

 

 

 

 

Transition Table

	Input	a	b
Step 1: State z1	z1=x1+y1	z2=x2+y1	z3=x1+y2
Step 2: State z2	z2=x2+y1	Z4=x3+y1	Z3=x1+y2
Step 3: State z3	z3=x1+y2	Z2=x2+y1	Z3=x1+y2
Step 4: State z4	z4=x3+y1	Z4=x3+y1	Z5=x3+y2
Step 5: State z5	z5=x3+y2	Z4=x3+y1	Z5=x3+y2

 

 

 

 

 

 

 

Step 1:

 

Step 1: State z1

z1=x1+y1

z2=x2+y1

z3=x1+y2

 

 

Step 2:

Step 2: State z2

Z=x2+y1

Z4=x3+y1

Z3=x1+y2

 

Step Final: