Question

Given the following FAs for the language {a} and {b}: construct the FA that is product for the language {a} +{b}. Show the transition table and draw the transition diagram convert your FA from problem 1(an FA is also a TG) into a regular expression (show the steps that you take).

Theory of Computation. Please show all work.

Answer 1

for lang a the trans table

	a	b
-x1(start state)	+x2	x3
+x2	x3	x3
x3	x3	x3

for lang b the tran table

	a	b
-y1	y3	y2
+y2	y3	y3
y3	y3	y3

we have to cmbine these table.for combining follow the steps

1st step: Design DFA for both languages and name their state Q₀, ...

2nd step : Rename every state in both DFA i.e. rename all states in DFA as Q₀ , Q₁ , Q₂ , Q₃ , ... assuming you have started with subscript 0 that means none of the state have same name

3rd Step: construct transition table(?) by using following steps

   3a. Take start state of both DFA(DFA1 , DFA2) and name them as Q_{[ i , j ]} where i is subscript of start state of 1st DFA and j is subscript of start state of 2nd DFA . i.e. Q_i is start state of 1st DFA and Q_j is start state of 2nd DFA and mark Q_{[i , j]}as start state of combined DFA.

   3b. Map state of both DFA as
           if ?(Q_i,a_k) = Q_p1 and ?(Q_j,a_k) = Q_p2 , where Q_p1 belongs to DFA1 and Q_p2 belongs to DFA2 then ?(Q_{[ i , j ]} , a_k) = Q_[p1,p2]

   3c. fill entire table while there is any Q_[i,j] remaining in transition table.

4th step: Construct final state table

For AND case final state would be all Q_{[i , j]} where Q_i and Q_j is final state of DFA1 and DFA2.
For OR case final state would be all Q_{[i , j]} where Q_i or Q_j is final state of DFA1 and DFA2.

5th step: Rename all Q_{[i , j]} (uniquely) and draw DFA this will be your result .

when combining the tran table will be

	a	b
Q[-x1,-y1]	Q[+x2,y3]	Q[x3,+y2]
Q[-x1,+y2]	Q[+x2,y3]	Q[x3,y3]
Q[-x1,y3]	Q[+x2,y3]	Q[x3,y3]
Q[+x2,-y1]	Q[x3,y3]	Q[x3,+y2]
Q[+x2,+y2]	Q[x3,y3]	Q[x3,y3]
Q[+x2,y3]	Q[x3,y3]	Q[x3,y3]
Q[x3,-y1]	Q[x3,y3]	Q[x3,+y2]
Q[x3,+y2]	Q[x3,y3]	Q[x3,y3]
Q[x3,y3]	Q[x3,y3]	Q[x3,y3]

by combining the table will be formed in this way.

rename the states as

Q[-x1,-y1] asQ0

Q[-x1,+y2]asQ1

Q[-x1,y3]asQ2

Q[+x2,-y1]asQ3

Q[+x2,+y2]asQ4

Q[+x2,y3]asQ5

Q[x3,-y1]asQ6

Q[x3,+y2]asQ7

Q[x3,y3]asQ8

0 Ca

where Q0 is the intial state

and the reg exp is

a(ab)ab*+a(ab)ab*+a(ab)*+ab(ab)*+a(ab)*+ab(ab)*+ab(ab)*+a(ab)*+ab(ab)*+b(ab)ab*+b(ab)ab*+b(ab)ab*