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.