Assignment 2 (Regular Expressions, Automata, Conversions)

1. Consider the following languages over alphabet { a, b }:

   L1 = set of words that start and end with the same symbol

   L2 = set of words of odd length

   The DFAs for L1 and L2 are shown below:

   

   Construct DFAs for the following languages:

   1. L1 ∪ L2
   2. L1 . L2
   3. L1^*

   Hint: You may construct intermediate NFAs and then use RMET and NTD algorithms to convert to DFAs. For the ∪ language, you may use the Product DFA construction.

2. Use the MIN algorithm to minimize the following DFA:

   start A
   final C F I
   trans A:0:B
   trans A:1:B
   trans B:0:C
   trans B:1:F
   trans C:0:D
   trans C:1:H
   trans D:0:E
   trans D:1:H
   trans E:0:F
   trans E:1:I
   trans F:0:G
   trans F:1:B
   trans G:0:H
   trans G:1:B
   trans H:0:I
   trans H:1:C
   trans I:0:A
   trans I:1:E
   

3. Implement the following methods in NFA.py and DFA.py. Also, write the driver programs to test these methods (RMET.py and MIN.py)

     # in NFA.py
     # removes empty-transitions
     def rmet(self):
       pass
   
     # in DFA.py
     # return union of DFAs (implement the product DFA method)
     def union(self,dfa2):
       pass
   
     # in DFA.py
     # minimize the DFA (For Graduate and Honors students)
     def minimize(self):
       pass
   

   $ python3 RMET.py ne1.nfa 
   sigma {'a', 'b'}
   
   INPUT NFA
   start q0
   final q2 
   trans q1:b:q2
   trans q1::q4
   trans q0:a:q3
   trans q0::q1
   trans q3:b:q4
   trans q3::q1
   trans q4::q5
   
   OUTPUT NFA-without-empty
   start q0
   final q2 
   trans q1:b:q2
   trans q0:a:q5
   trans q0:a:q3
   trans q0:a:q4
   trans q0:a:q1
   trans q0:b:q2
   trans q3:b:q5
   trans q3:b:q4
   trans q3:b:q2
   

   The UNION method can be tested with the following driver program:

   $ more Union.py
   from DFA import *
   
   def main():
     dfa1 = DFA({'a','b'},{'q0','q1'})
     dfa1.set_start('q0')
     dfa1.set_final({'q0'})
     dfa1.add_transition('q0','a','q1')
     dfa1.add_transition('q0','b','q1')
     dfa1.add_transition('q1','a','q0')
     dfa1.add_transition('q1','b','q0')
   
     dfa2 = DFA({'a','b'},{'q2','q3'})
     dfa2.set_start('q2')
     dfa2.set_final({'q3'})
     dfa2.add_transition('q2','a','q3')
     dfa2.add_transition('q2','b','q2')
     dfa2.add_transition('q3','a','q3')
     dfa2.add_transition('q3','b','q2')
   
     dfa = dfa1.union(dfa2)
   
     print(dfa)
   
   main()
   $
   $ more d1-nonmin.dfa 
   start A
   final C
   trans A:0:B
   trans A:1:F
   trans B:0:G
   trans B:1:C
   trans C:0:A
   trans C:1:C
   trans D:0:C
   trans D:1:G
   trans E:0:H
   trans E:1:F
   trans F:0:C
   trans F:1:G
   trans G:0:G
   trans G:1:E
   trans H:0:G
   trans H:1:C
   $
   $ python3 MIN.py d1-nonmin.dfa 
   
   OUTPUT minimized DFA
   start A_E
   final C 
   trans D_F:1:G
   trans D_F:0:C
   trans G:1:A_E
   trans G:0:G
   trans C:1:C
   trans C:0:A_E
   trans A_E:1:D_F
   trans A_E:0:B_H
   trans B_H:1:C
   trans B_H:0:G
   $