Assignment 1 (Regular Expressions, Automata, NFA to DFA Implementation)

1. Write regular expressions and construct DFAs for the following languages over alphabet { a, b }:
   1. set of words that start with 'a' and has 2 or fewer b's.
   2. set of words of odd length that end with 'b'.
   3. set of words that have at least 2 a's and 2 b's.

2. Prove that the set of integers (without leading zeros) that are divisible by both 3 and 5 is regular. Note that +30, 045, -015 are not elements of the language and -45, 15, 60 are elements of the language.

   Class design for Automata algorithms implementation

   FALexer.py

   FAParser.py

3. Using the PLY package, implement the NFA to DFA conversion algorithm. We will assume the input NFA description is stored in a file. Some NFAs and their corresponding DFAs are shown below:

   $ more n1.nfa 
   start q0
   final q1 q3
   trans q0:a:q1
   trans q0:a:q2
   trans q2:b:q3
   trans q3:a:q2
   $
   $ python3 NTD.py n1.nfa 
   start q0
   final q3 q1_q2
   trans q0:a:q1_q2
   trans q0:b:EMPTY
   trans q1_q2:a:EMPTY
   trans q1_q2:b:q3
   trans EMPTY:a:EMPTY
   trans EMPTY:b:EMPTY
   trans q3:a:q2
   trans q3:b:EMPTY
   trans q2:a:EMPTY
   trans q2:b:q3
   $
   $ more n2.nfa
   start q0
   final q1
   trans q0:a:q0
   trans q0:b:q0
   trans q0:a:q1
   $
   $ python3 NTD.py n2.nfa 
   start q0
   final q0_q1 
   trans q0:a:q0_q1
   trans q0:b:q0
   trans q0_q1:a:q0_q1
   trans q0_q1:b:q0
   $
   $ more n3.nfa
   start q0
   final q2 q3 q4
   trans q0:a:q1
   trans q0:a:q4
   trans q0:b:q3
   trans q1:a:q1
   trans q1:b:q2
   trans q4:b:q4
   $
   $ python3 NTD.py n3.nfa 
   start q0
   final q2 q2_q4 q3 q4 q1_q4 
   trans q0:b:q3
   trans q0:a:q1_q4
   trans q3:b:EMPTY
   trans q3:a:EMPTY
   trans q1_q4:b:q2_q4
   trans q1_q4:a:q1
   trans EMPTY:b:EMPTY
   trans EMPTY:a:EMPTY
   trans q2_q4:b:q4
   trans q2_q4:a:EMPTY
   trans q1:b:q2
   trans q1:a:q1
   trans q4:b:q4
   trans q4:a:EMPTY
   trans q2:b:EMPTY
   trans q2:a:EMPTY
   

   The output DFA should be displayed in the same format as the input. You must build a Lexer and a Parser that reads input NFA in the file and stores the NFA in a Python data structure. Then, the program should implement the NFA to DFA conversion algorithm and print the DFA to screen (in same format as input NFA).