CS/ECE 374 A (Spring 2022) Conflict Midterm Exam 1
Instructions:
Date/Time: Feb 22 Tuesday 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 NFA accepts the language 2∗0(10 + 3)∗ (over the alphabet {0, 1, 2, 3}). 23
(b) For every DFA M , there exists a regular expression that generates the language accepted by M.
(c) For every language L, if L is accepted by a DFA M with n states where exactly one state is an accepting state, then LR = {wR : w ∈ L} is accepted by a DFA with n states obtained by reversing the direction of all transitions and reversing the role of the start state and the single accepting state in M.
(d) For every pair of languages L1 and L2, we have (L1 ∪ L2)∗L∗1 = (L1 ∪ L2L∗2)∗.
(e) The language {x ∈ {0, 1}∗ : x contains 0n1n as a substring for some n ≥ 374} is regular.
(f) The language {x ∈ {0, 1}∗ : x contains 0n1n0n as a substring for some n ≤ 374} is reg- ular.
(g) For the language {x ∈ {0, 1}∗ : |x| is divisible by 2022}, there exists a fooling set of size 2022.
(h) Every context-free language is regular.
(i) The language generated by the context-free grammar S → 0S0 | 0S1 | 1S0 | 1S1 | ε 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: 1(010)∗(11)∗ + 010∗.
Justification is not required.
(b) [8 pts] Draw an NFA for the following language:
{x ∈ {0, 1}∗ : (number of 0’s in x is divisible by 3) or (x does not end with 0110)}. 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+1)∗00 + (0+1)∗11.
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] Show that the following language is regular:
{0i1j :jisdivisiblebyi,and1≤i≤2022}.
(b) [8 pts] Describe a DFA for the following language:
{0n1m : n + m is not divisible by 2022}.
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 = {0i1j2k : k ≥ min{i,j}, i,j,k ≥ 0}.
(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.) [Hint: k≥min{i,j}iffk≥iork≥j.]
5. [15 pts] Given a language L over the alphabet Σ, define insert-fifth(L)={xay: xy∈L, x,y∈Σ∗, a∈Σ, |x|=4}.
(For example, if 1010010011 ∈ L, then 10100010011 and 10101010011 are both in insert-fifth(L).)
(a) [3 pts] For L = (01)∗, describe insert-fifth(L) by a regular expression.
(b) [12 pts] Prove (in general) that if L is regular, then insert-fifth(L) is regular.
[Hint: given an NFA (or DFA) M = (Q, Σ, s, δ, A) for L, construct an NFA M′ = (Q′, Σ, s′, δ′, A′) for insert-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