Give algorithms and state their time complexities to determi

Give algorithms (and state their time complexities) to determine whether for a given pair of finite automata:

a) they both accept the same language

b) the intersection of their languages is empty

d) the intersection of their languages is finite

e) the difference of their languages is finite

Solution

a) both accept same language -

Algorithm -

Given two Deterministic Finite Automation - on same alphabet, we intend to
determine if they accept the same language.
M1 = (Q1, , 1,s1, F1)
M2 = (Q2, , 2,s2, F2)
Is L(M1) = L(M2) ?

The simple Algorith for it would be as -

I)Minimize M1 and M2 to get canonical DFAs, M`1 and M`2.
i)Time complexity = O(||n log n)

II) Check if M`1 and M`2 are equivalent.
i)Time complexity = O(||m)
where m is the number of states in M`1 (or M`2).

Overall complexity = O(||n log n)

b)the intersection of their languages is empty

automaton usually is not minimal (e.g. the intersection might be just an empty language).

Shall illustrte a systematic way for creating automatons for intersection of languages.
Let AA and BB be the input automatons. The states of new automaton will be all pairs of states of AA and BB, that is SAB=SA×SBSAB=SA×SB, the initial state will be iAB=iA,iBiAB=iA,iB, where iAiA and iBiB are the initial states of AA and BB, and FAB=FA×FBFAB=FA×FB where FXFX denotes the set of accepting states of XX. Finally, the transition function ABAB is defined as follows for any letter and states p1,p2SAp1,p2SA, q1,q2SBq1,q2SB:

p1,q1AB p2,q2 iff p1A p2andq1B q2
p1,q1AB p2,q2 iff p1A p2andq1B q2
Please note down, that such automaton usually is not minimal (e.g. the intersection might be just an empty language).
Also it might be useful (but it is not necessary) to make input automatons minimal since the output is quadratic in size.

c)The intersection of their language is sigma *

• states of And(M1, M2) are all ordered pairs (q1, q2) with
q1 StatesM1
and q2 StatesM2
• alphabet of And(M1, M2) is the common alphabet of M1 and M2
• (q1, q2)
a (q
0
1
, q0
2
) in And(M1, M2) iff q1
a q
0
1
in M1 and
q2
a q
0
2
in M2
• start state of And(M1, M2) is (sM1
, sM2
)
• (q1, q2) accepting in And(M1, M2) iff q1 accepting in M1 and q2
accepting in M2

d)the intersection of their languages is finite.

And(M1, M2)
• states of And(M1, M2) are all ordered pairs (q1, q2) with
q1 StatesM1
and q2 StatesM2
• alphabet of And(M1, M2) is the common alphabet of M1 and M2
• (q1, q2)
a (q
0
1
, q0
2
) in And(M1, M2) iff q1
a q
0
1
in M1 and
q2
a q
0
2
in M2
• start state of And(M1, M2) is (sM1
, sM2
)
• (q1, q2) accepting in And(M1, M2) iff q1 accepting in M1 and q2
accepting in M2