CS/ECE 374 A (Spring 2022) Midterm Exam 1
Instructions:
Date/Time: Feb 21 Monday 7:00pm–9:30pm Central Time.
Except for your one double-sided handwritten 8.5′′ × 11′′ cheat sheet, exams are closed- everything. In particular: No medically unnecessarily electronic devices are allowed in exams, including smart watches and headphones/earbuds.
Copyright By PowCoder代写 加微信 powcoder
You will write your solutions on paper, scan your solutions using a scanning app, convert your scans to PDF, and upload the PDF to Gradescope. (You are not allowed to write your solutions on tablets, unlike in some past semesters.) Gradescope will only accept PDF submissions. Please make sure your solution to each numbered problem starts on a new page of your submitted PDF file. Please do not scan your cheat sheets or scratch paper.
You have two hours (i.e., 120 minutes) to write your solutions. We are providing 30 minutes at the end of each exam period for students to scan and upload their exams, and to deal with any unexpected technical difficulties that may arise. Gradescope will stop accepting submissions for each midterm precisely at 9:30pm. We will not accept submissions after the Gradescope deadline. All work on the exam must stop 30 minutes before the Gradescope deadline, i.e., at 9:00pm.
Please make sure that your scans are clear and easy to read. We very strongly recommend that you write with black ink on unlined white paper. Submissions consisting of raw photos or low-quality scans will be penalized.
If you are ready to scan your solutions before 9:00pm, send a private message to the host of your Zoom call (“Ready to scan”) and wait for confirmation before leaving the Zoom call.
If something goes seriously wrong during the exam, send email to Timothy as soon as possible explaining the situation. If you have already finished the exam but cannot submit to Gradescope for some reason, include a complete scan of your exam as a PDF file in your email. If you are in the middle of the exam, send email to Timothy, continue working until the time limit, and then send a second email with your completed exam as a PDF file. Please do not email raw photos.
You are reminded about the course’s, the department’s, and the university’s academic in- tegrity policies.
Avoid the deadly sins. Write complete solutions, not examples. Declare all your variables. Write concisely and precisely.
Good luck!
1. [27 pts] True or false, with justifications. For each statement below, determine whether the statement is “True” or “False”. You are required provide a short explanation (one or two sentences) for each of your answers.
(a) The following DFA accepts the language 0∗(11)∗10(0 + 1)∗.
0,1 q1 0 q2
(b) For every regular expression r, there exists a DFA that accepts the language generated by r.
(c) For every language L, if L is accepted by a NFA with n states, then the complement of L is accepted by some NFA with at most 2n states.
(d) For every pair of languages L1 and L2, we have (L∗1L2)∗ = (L1 ∪ L2)∗.
(e) The language {x ∈ {0, 1}∗ : x contains 0n1n0n as a substring for some n ≤ 374} is reg-
(f) For every language L, if L is not regular, then {xyz : x ∈ Σ∗,y ∈ L,z ∈ Σ∗} is not regular.
(g) For the language {x ∈ {0, 1}∗ : |x| is divisible by 2022}, there exists a fooling set of size 2023.
(h) Every regular language is context-free.
(i) The language generated by the context-free grammar S → 0S1 | 0S | S1 | 1 is regular.
2. [24 pts]
(a) [8 pts] Draw an NFA (i.e., a nondeterministic finite automaton, possibly with ε-
transitions) for the language described by the following regular expression: (01 + 1)∗(0∗1 + 1∗0)(10 + 0)∗.
Justification is not required.
(b) [8 pts] Draw an NFA for the following language:
{x ∈ {0, 1}∗ : (x begins with 0101) or (x does not end with 0101)}. Justification is not required.
(c) [8 pts] Draw a DFA (i.e., a deterministic finite automaton) for the language described by the following regular expression:
0(0+1)∗0 + 1(0+1)∗1.
If you are using known methods from class, indicate which one(s). If not, briefly explain
the meaning of the states in your DFA. 2
3. [16 pts]
(a) [8 pts] Give a regular expression for the following language:
{0n1m : n + m is divisible by 5}. Justification is not required.
(b) [8 pts] Describe a DFA for the following language:
{0i1j :1≤i≤2022andjisnotdivisiblebyi}.
Do not draw this DFA (there are too many states!). Instead, give a mathematically precise description of the states Q, the start state s, the accepting states A, and the transition function δ. Briefly describe the meaning of the states in your DFA (proof of correctness is not required).
4. [18 pts] Define the following language: L={x∈{0,1}∗ : xhasoddlengthatleast3,and
the first symbol, the middle symbol, and the last symbol are the same}. The middle symbol refers to the symbol at position ⌈|x|/2⌉ in the string x. (For example,
10011101011 is in L, but 1010101 is not in L.)
(a) [10 pts] Prove that L is not regular, by using the fooling set method.
(b) [8 pts] Show that L is context-free, by giving a CFG. Briefly explain the meaning of each non-terminal. (You do not need to provide justification, or proof of correctness.)
5. [15 pts] Given a language L over the alphabet Σ, define delete-fifth(L)={xy: xay∈L, x,y∈Σ∗, a∈Σ, |y|=4}.
(For example, if 10100110011 ∈ L, then 1010010011 ∈ delete-fifth(L).)
(a) [3 pts] For L = (01)∗, describe delete-fifth(L) by a regular expression.
(b) [12 pts] Prove (in general) that if L is regular, then delete-fifth(L) is regular.
[Hint: given an NFA (or DFA) M = (Q, Σ, s, δ, A) for L, construct an NFA M′ = (Q′, Σ, s′, δ′, A′) for delete-fifth(L). Give a mathematically precise description of Q′, s′, δ′, and A′ in your construction, and a brief explanation of how your NFA works. You don’t have to provide meaning of the states or proof of correctness of your NFA.]
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com