Solutions to Practice Problems for Exam 1

1. For each of the following languages over alphabet { a, b }, write a regular expression and construct a DFA:

   • L = { a, aab, bab }

     

   • L = words in which the number of b's is divisible by 3.

     

   • L = words in which the third last symbol is an a.

     

2. Consider the following NFA with empty transitions:

   start p
   final r
   trans p:a:p
   trans p:b:q
   trans p:c:r
   trans q::p
   trans q:a:q
   trans q:b:r
   trans r::q
   trans r:a:r
   trans r:c:p
   

   • Compute the e-closure for each state

   • List all the strings of length 3 or less accepted by the NFA.

   • Convert NFA to DFA

   

3. Using Arden's Lemma, derive the regular expression for the following DFA:

   start q0
   final q0
   trans q0:a:q0
   trans q0:b:q1
   trans q1:a:q1
   trans q1:b:q2
   trans q2:a:q2
   trans q2:b:q0
   

   

4. Minimize the following DFA:

   start q0
   final q1 q2 q5
   trans q0:a:q1
   trans q0:b:q2
   trans q1:a:q3
   trans q1:b:q4
   trans q2:a:q4
   trans q2:b:q3
   trans q3:a:q5
   trans q3:b:q5
   trans q4:a:q5
   trans q4:b:q5
   trans q5:a:q5
   trans q5:b:q5