CSE 105 Spring 2021
Homework 2
CS计算机代考 One member of the group should upload your group submission to Gradescope. During the submission process, they will be prompted to add the ···
Instructions CS计算机代考
One member of the group should upload your group submission to Gradescope. During the submission process, they will be prompted to add the names of the rest of the group members. All group members’ names and PIDs should be on each page of the submission.
Your homework must be typed. We recommend that you submit early drafts to Gradescope so that in case of any technical diffiffifficulties. At least some of your work is present. You may update your submission as many times as you’d like up to the deadline.
Your assignments in this class will be evaluated not only on the correctness of your answers. But on your ability to present your ideas clearly and logically. You should always explain how you arrived at your conclusions. Using mathematically sound reasoning. Whether you use formal proof techniques or write a more informal argument for why something is true. Your answers should always be well-supported. Your goal should be to convince the reader that your results and methods are sound.
Problems that are marked with * are optional and will not be graded. Reading Sipser Sections 1.1, 1.2 1.3 CS计算机代考
(a) Draw the state diagram of this DFA.
(b) Describe the language recognized by this DFA (include brief justifification of your answer).
(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 NFA, M, whose state diagram is given by:
a) Describe the language L(M)(include brief justifification of your answer). CS计算机代考
b) Describe in your own words the “role” of each of the states.
c) Write a regular expression that describes L(M). (please explain your reasoning.)
d) ∗ For c and d, if your answer is no, give a NFA that descibes the language obtained by applying that operation (swapping a’s and b’s or reversing) to all elements of L(M)
e) ∗ Give a DFA that describes the same language as L(M).
3.(15 points) CS计算机代考
For each problem, the alphabet will be Σ = {0, 1, 2} and we will be considering each string to be an integer base 3. For each part include brief justifification of how your machine works.
(a) Design a DFA that recognizes the language: {w ∈ {0, 1, 2}∗ | w in base 3 is congruent to 0 mod 2.} (Note: this set does include the empty string.)
(b) Design a regular expression that describes the language: {w ∈ {0, 1, 2}∗ | w in base 3 is congruent to 0 mod 2.} (Note: this set does include the empty string.)
(c) Design a DFA that recognizes the language: {w ∈ {0, 1, 2}∗ | w in base 3 is congruent to 1 mod 4.} (Note: this set does not include the empty string.)
(d) ∗ Design a regular expression that describes the language: {w ∈ {0, 1, 2}∗ | w in base 3 is congruent to 1 mod 4.} (Note: this set does not include the empty string.)
4.(20 points) CS计算机代考
Given a word w in an alphabet Σ, defifine the reverse of w, denoted wR, to be the word obtained by reversing the order of the characters appearing in w. That is, if w = w1w2 . . . wn−1wn, then wR = wnwn−1 . . . w2w1. Further defifine the reverse of a language L, denoted LR, to be the set of all reverses of words in L. That is LR = {wR : w ∈ L}.
(a) Give a constructive proof using fifinite automata to show that the set of regular languages is closed under the operation of taking reverses.
(b) Give a constructive proof using regular expressions to show that the set of regular languages is closed under the operation of taking reverses.
(c) ∗ Defifine an operation on languages that is difffferent than the ones we have already given. Prove whether regular languages are closed under your operation or not.
更多代写：C++代写 GRE代考 lab代写 代写essay 作业代写 统计网课代修
