Description
Problem 1. ) Complete the TopHat worksheet titled Spring 2020 HW1.1. There are a total of 10 questions, each worth 2 points.
Problem 2. (12+6+2 points, for a total of 20 points) Let DFA D1 be defined as follows:
0
D1: 0,1
0,1
2(a) Provide the formal description (Q,Σ,δ,s,F) of the DFA D1.
2(b) Let s1 = 001. Provide the computation of D1 on input s1.
2(c) Is s1 ∈ L(D1)?
Problem 3. (12+8 points)
Prove the following language L1 is regular by constructing a DFA that will recognize the language L1 defined by:
L1 = {w ∈ {0,1}∗ |,w has odd length or ends with 1}.
When designing a DFA to recognize L1, you must provide an explanation for how your automata works/what your algorithm is. One way to do this is to explain what each state is recording and how that plays into your overall solution (similar to how this was done in lecture).
