Python

The Intersection Code

The objective is to show that the intersection of two regular languages is regular. A DFA is easily complemented, so it is true that the intersection is regular by De Morgan's law, A AND B = NOT(NOT A OR NOT B). However the OR operation takes the two complemented DFA's and makes an NFA, which then has to be converted back to DFA's for the final complement. This can exponentiate the number of states.

In this exercise we build a intersection machine directly. It is in the sprit of the NFA to DFA construction, in that we will simulate the computation of the two DFAs in parallel. We create product machine that has states form as pars, (,)(s,t), were s is a state from the first machine, and t is a state from the second machine. To be in state (,)(s,t) means that on the input used up to that moment in the computation, the first machine would be in state s and the second in state t.

There are several possibilities for the accepting states of a product machine, but to calculate the intersection of the two languages, a state (,)(s,t) is accepting in the product machine, if s is accepting in the first machine and t is accepting in the second mahince.

def functions cartesian_product() , do_transitions() , and construct() to solve the sample test

class IntersectionDFA: """ given two DFA descriptions, create a DFA description that accepts the intersection of the languages of the given DFA alphabets must be the same the two DFA's presented are in our standard form; the output DFA makes the change that states are 2-tuples of states. since tupes are immuatable, as are strings, this change does not affect any coding. output: 'states':list(tuple(string,string)) 'alphabet':list(character) 'transitions':dict(tuple(tuple(string,string),character):tuple(string,string)) 'start':tuple(string,string) 'accept':list(tuple(string,string)) input: 'states':list(string) 'alphabet':list(character) 'transtions':dict(tuple(string,string):string) 'start':string 'accept':list(string) """ def __init__(self, dfa1, dfa2): self.dfa1 = dfa1 self.dfa2 = dfa2 self.states = [] self.alphabet = [] self.transitions = {} self.start = None # an empty 2-tuple should go here, but those do not exist self.accept = [] # the alphabets must be the same assert set(dfa1['alphabet']) == set(dfa2['alphabet'])

def cartesian_product(self,l1,l2): """ given l1, l2 each a list(string), return the cartesian product list(tuple(string,string)) of all pairs of strings, the first from the first list, the second from the second list """ pass # write code return res # replace None as well def do_transitions(self): """ create transitions of the Intersection DFA. - go through all state,letter pairs of the Intersection DFA - for each pair, refer to the transitions in dfa1 and dfa to find the resulting state in the Intersection DFA """ pass # write code def construct(self): """ construct the Intersection DFA. - what alphabet does it have - what start state does it have - what states does it have - what accept states does it have - what transitions does it have """ pass # write code return { 'states':self.states, 'alphabet':self.alphabet, 'transitions':self.transitions, 'start':self.start, 'accept':self.accept }

# a sample machine

X = { 'states':['X1','X2','X3','R'], 'alphabet':['a','b'], 'transitions':{ ('X1','b'):'X1',('X1','a'):'X2', ('X2','b'):'R',('X2','a'):'X3', ('X3','b'):'X3',('X3','a'):'R', ('R','a'):'R',('R','b'):'R' }, 'start':'X1', 'accept':['X3'] } Y = { 'states':['Y1','Y2','Y3','R'], 'alphabet':['a','b'], 'transitions':{ ('Y1','a'):'Y1',('Y1','b'):'Y2', ('Y2','a'):'R',('Y2','b'):'Y3', ('Y3','a'):'Y3',('Y3','b'):'R', ('R','a'):'R',('R','b'):'R' }, 'start':'Y1', 'accept':['Y3'] }

# a sample test

tests = [ ('aabb',True),('aabb',True), ('',False),('a',False),('b',False), ('bbbaa',False),('aabbb',False) ]

# want verbose verbose = True test_machine(IntersectionDFA(X,Y).construct(),tests)

# further testing ...