CSC444 Homework #3 Answers

1. Give an NFA that recognizes the language L:

     L = all strings over { 0, 1} that contain a pair of 1's that are
         separated by an odd number of symbols. 
   
   Examples of strings in L
   101
   1001001
   01001000100001
   10010000100001
   
   
   Examples of strings not in L
   11
   1001
   100001
   0011000
   001001000
   00100001000
   
   
   

   Answer:

   

2. TextBook exercises 1.16 and 1.22a

   1.16 Convert each of the following NFA's to equivalent deterministic DFA's. Use the subset construction as in this example.

   1. 

      Answer: q₀ = {1}, q₁ = {1,2}, q₂ = {2}, q₃ = {}

      

   2. 

      Answer: q₀ = {1,2}, q₁ = {1,2,3}, q₂ = {2,3}, q₃ = {}

      

   1.22a. In certain programming languages, comments appear between delimiters such as /# and #/. Let L be the language of all valid delimited comment strings. A member of L must begin with /# and end with #/ but have no intervening #/. For simplicity, we'll say that the alphabet is
   {a, b, /, #}.

   Give a DFA that recognizes L.

   Valid strings in L
   /#abababaaababa#######/
   /#ababab##aa#/
   /####################/
   /#///////#/
   /#/#/
   /##/
   
   Strings not in L
   /#/
   /##/#/
   /#ab#/ba#/
   
   

   Answer: