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

SOLUTIONS

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'.

      Regular Expression is:

      

      Equivalent NFA

      

      Applying NTD conversion to NFA gives us the following DFA:

      

   3. set of words that have at least 2 a's and 2 b's.

      Regular Expression is:

      

      DFA for words with at least 2 a's:

      

      DFA for words with at least 2 b's:

      

      ProductDFA for words with 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.

   NFA for L1 = set of integers with no leading zeros is shown below:

   

   NFA for L2 = set of integers divisible by 5 (may have leading zeros) is shown below:

   

   NFA for L3 = set of integers divisible by 3 (may have leading zeros) is shown below:

   

   Note L = L1 ∩ L2 ∩ L3

   Since L1, L2, and L3 are regular (we have constructed NFAs for each) and since regular languages are closed under intersection, L is regular.