# 算法代写 | CSE 105 Winter 2021 Homework 2

这个作业是完成DFA相关的算法

CSE 105 Winter 2021

Homework 2

1. (10 points) Draw the DFA that is described by the formal definition:

({q0, q1, q2, q3, q4}, {0, 1, 2}, δ, q0, {q0})

with δ defined by

δ(qi

, 0) = qi

,

δ(qi

, 1) = q(i+1 mod 5),

and

δ(qi

, 2) = q(i−1 mod 5)

(a) Draw the state diagram of your DFA in JFLAP, export the image as a png or jpg file, and include

it as part of your submission.

(b) Describe the language recognized by this DFA.

(c) ∗

Is it possible to construct a DFA that recognizes this language with fewer states? If not, explain

why not. If so, then draw it using JFLAP. What if we took a NFA instead of a DFA?

2. (10 points) Consider the DFA, M, whose state diagram is given by:

1

a) Describe the language L(M).

b) If w ∈ L(M), will the string obtained by swapping a’s and b’s in w also be in L(M)? Explain your

answer.

c) If w ∈ L(M), will the string w

R (the reverse of w) also be in L(M)? Explain your answer

d) Describe in your own words the “role” of each of the states.

e) Write a regular expression that describes L(M). (please explain your reasoning.)

f) ∗ For c and d, if your answer is no, give a DFA that describes the language obtained by applying

that operation (swapping a’s and b’s or reversing) to all elements of L(M)

g) ∗ Can you create a NFA for L(M) that uses fewer states?

3. (10 points) Consider the DFA, M, whose state diagram is given by:

2

a) Describe the language L(M).

b) If w ∈ L(M), will the string obtained by swapping a’s and b’s in w also be in L(M)? Explain your

answer.

c) If w ∈ L(M), will the string w

R (the reverse of w) also be in L(M)? Explain your answer

d) Describe in your own words the “role” of each of the states.

e) Write a regular expression that describes L(M). (please explain your reasoning.)

f) ∗ For c and d, if your answer is no, give a DFA that descibes the language obtained by applying

that operation (swapping a’s and b’s or reversing) to all elements of L(M)

g) ∗ Can you create a NFA for L(M) that uses fewer states?