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.

Problem 4

The algorithm for converting a finite automaton to a regular expression described in class and in the notes works by removing one state at a time from this NDFA-esque diagram that allows transitions to be labeled with regular expressions. Specifically, the $i$th iteration through the outer "for" loop removes state $q_i$. The machine below is the result of running the algorithm through iterations $i=1$, $2$ and $3$. Show what the machine looks like after the $i=4$ iteration removes state $q_4$.