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.