Let 𝑀 be the 5-state NFA with 𝜖-transitions shown in the diagram below.…

Key observations:

• There are epsilon-transitions from the start state to two subcomponents: one whose accepting state is labeled 2 (the upper component) and one that reaches accepting state 5 via a 1 (the lower component).

• Upper component (states 2 and 3 with 0-transitions): starting at state 2 (which is accepting) you can accept the empty string or take 0 to state 3 and alternate on 0. Thus the upper component accepts strings with an even number of zeros (including the empty string), i.e. (00)*,

• or from the upper component you can take an odd number of zeros (any expression of the form 0(00)* = (00)*0) to land in state 3 and then take the epsilon to state 5 and continue with the lower component.

• Lower component (states 4 and 5 with 1-transitions): to reach the accepting state 5 from the lower branch you must read a leading 1 (from state 4 to 5), and once at state 5 reading pairs of 1s (via 5->4->5) keeps you in the accepting state. So the lower branch accepts 1(11)*. Also, if you arrive at 5 from the upper part (via an odd number of zeros and an epsilon), you can then accept (11)*.

Assembling the two behaviours yields:

1. Even-number-of-zero strings (including the empty string): (00)*

2. Strings that go to the 1-block either by a leading 1 from the lower branch or by an odd number of zeros from the upper branch, followed by any number of 11 pairs: (1 + 0(00)*) (11)*

Therefore the full regular expression for the language is:

(00)* + (1 + 0(00)*)(11)*

Remarks: 0(00)* is equivalent to (00)*0 and denotes all strings of zeros of odd length; this is why the expression matches the behaviour of taking an odd number of zeros to reach the accepting ones-component.