Class 18: Homework
You must print this sheet out and write/type answers on it!
-
Draw the expression tree for the regular expression
b(a|bb)*b|λ.
[Note: the tree is not unique! There are two
possibilities.]
-
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.
-
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.