[Solved] CSE 396-Assignment 1

Problem 1. ( Complete the TopHat worksheet )

Problem 2. Let DFA D₁ be defined as follows:

0

D₁: 0,1

0,1

2(a) Provide the formal description (Q,,,s,F) of the DFA D₁.

2(b) Let s₁ = 001. Provide the computation of D₁ on input s₁.

2(c) Is s₁ L(D₁)?

Problem 3. (12+8 points)

Prove the following language L₁ is regular by constructing a DFA that will recognize the language L₁ defined by:

L₁ = {w {0,1} |,w has odd length or ends with 1}.

When designing a DFA to recognize L₁, 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 .