Menu

Class 18: Homework


You must print this sheet out and write/type answers on it!

  1. Draw the expression tree for the regular expression b(a|bb)*b|λ. [Note: the tree is not unique! There are two possibilities.]
     
  2. Draw the expression tree for the regular expression ((a|λ)(b|λ))* and draw the NDFA that results from following the Regular-exression-to-NDFA conversion algorithm from the notes.
     
  3. The NDFA from the above problem should have a λ-cycle. Show the machine that results from following our λ-cycle elimination algorithm. Just remove the λ-cycle, not the other λ-transitions.