Hello, if you have any need, please feel free to consult us, this is my wechat: wx91due
CS172 Computability & Complexity Homework 1
Guidelines: Submit your solutions in pdf format on Gradescope by 5pm on Sep. 2. Solutions may be either typed in LATEX or Word (with either machine-drawn or hand-drawn diagrams) or written legibly by hand. Please be sure to begin the solution for each problem on a new page, and to tag each of your solutions to the correct problem. Take time to write clear and concise answers. You are encouraged to form small groups to work through the homework, but you must write up all your solutions on your own. Depending on grading resources, we reserve the right to grade a random subset of the problems and check off the rest; so you are advised to attempt all the problems.
(The LATEX source for this homework is provided in case you want to use it as a template. To draw a finite state automaton, we used the following website: https://madebyevan.com/fsm/; )
Q 1. Construct deterministic finite automata (DFAs) that accept each of the following languages.
In each case, give the state diagrams of the DFA fully and clearly. The alphabet in all parts in {0, 1}.(a) {w | w contains a 0 AND a 1}
(b) {w | w contains a 0 OR a 1}
(c) {w1w2 . . . wn | Pn i=1 wi ≡ 2 mod 4}
(d) {w | w starts with a 1 AND ends with a 1}
(e) {w | the length of w is at least 2}
(f) {w | w has an odd length AND an odd number of 1s}
(g) {w | w has an odd length OR an odd number of 1s}
(h) (extra credit) {w | w has the same number of 01 as 10}.
Q 2. In certain programming languages, comments appear between delimiters such as /# and #/. Let C be the language of all valid delimited comment strings. A member of C must begin with /# and end with #/ but have no intervening #/. For simplicity, assume that the alphabet for C is Σ = {a, b, /, #}. Give a DFA that recognizes C. (Briefly describe what each state “remembers”, without a formal proof.)
Q 3. (a) What is the language recognized by the following DFA over alphabet 0-1?
(b) Give a formal proof that the language recognized by the DFA is indeed the language you described in Item (a).
Hint: For each state q, write down a precise characterization of the set of input strings w that cause the DFA to end in state q. Then prove either by induction on the length of w or by a direct argument that these characterizations are correct.
Q 4. (a) Given a DFA M = (Q, Σ, δ, q0, F) that recognizes a language L, write the formal def- inition of the NFA that recognizes the reverse language L R that we saw in class MR = (Q′ , Σ, δ′ , Q′ 0 , F′ ).(Recall that L R is defined as L R = {w | w R ∈ L} and w R is the reverse of w, i.e., if w = w1w2 . . . wn then w R = wn . . . w2w1.)
(b) Prove that the NFA MR recognizes the language L R.
Hint: show that every string in L R is accepted by MR, and that every string accepted by MR is in L R.