Exercise 03

I will give non-regular exercises for you to try (remember, you must work on these besides following my lectures or read book sections!). These will not be graded. Solutions will be posted on D2L a bit later.

Problem 1

Let    = fa; bg. Construct a DFA for the following language:

(1.1) D = fwj every odd position of w is bg.



 Problem 2

Let    = fa; bg. Construct an NFA for the following language:

(2.1) C = fwj w has an even number of a0 s; or exactly two b0 sg.