算法代写 | 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?