Name: ____________________________________________________ Alpha: _____________________

Describe help received: _________________________________________________________________

Problem 1

Draw the expression tree for the regular expression b(a|bb)*b|λ. [Note: the tree is not unique! There are two possibilities.]
 

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

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