CS/ECE 374: Algorithms and Models of Computation, Spring 2021 Midterm 1 – March 1, 2021
• You can do hard things! Grades do matter, but not as much as you may think, but then life is uncertain anyway, so what.
• Don’t cheat. You know the student code but more importantly you won’t be proud later.
• Please read the entire exam before writing anything. There are 7 problems and they
Copyright By PowCoder代写 加微信 powcoder
are of equal value.
• This is a closed-book exam but you are allowed a 1 page (2 sides) cheat sheet that you have to upload along with your exam.
• You should write your answers on clean and clear white pages. After the exam is over you should upload a scan or a photo to Gradescope. If you have technical difficulties you can send the files via email to the course staff. Keep a copy of your written exam in case there are technical difficulties. Try to use different sheets for different problems to make it easier for processing.
• You have 150 minutes (2.5 hours) for the exam. This does not include the time for scanning the exam after finishing the writing. You have up to an additional half hour for scanning.
• Proofs are required only if we specifically ask for them.
• You may state and use (without proof or justification) any results proved in class or in the problem sets unless we explicitly ask you for one.
• Please contact the course staff if you run into difficulties with internet, Zoom, etc. You can send email or call/text the staff.
CS/ECE 374 Midterm 1 Spring 2021
1 Regular Expression
Give regular expressions for the following two languages.
• L1 = {w ∈ {0, 1}∗ | w does not have the substring 111}. The string 11001 is in L1 but not
• L2 ={w∈{0,1}∗ |all0blocksofwareofevenlength}. Recalla0blockisamaximal
non-empty substring of 0’s in the string. The string 0000100 is in L2 but not 001110. Briefly explain your regular expressions.
2 DFA Construction
Draw or describe a DFA for the language defined below. L={w∈{0,1}∗ |wendsin10and|w|isodd}.
Your DFA must have at most 6 states. Label the states and explain them. 3 Regular Expressions
Given a language L over alphabet Σ and string x ∈ Σ∗ we define the language insert(L, x) as the set of all strings w where w is obtained by taking a string w′ ∈ L and inserting x in w′ at some position. More formally insert(L, x) = {uxv | uv ∈ L}. For example if L = {CS374} and x = not then insert(L,x) = {notCS374,CnotS374,CSnot374,CS3not74,CS37not4,CS374not}. In this problem, assuming that L is regular, you will derive an algorithm that generates a regular expression r′ for insert(L, x) from regular expression r for L.
• For each of the base case of r = ,ε and r = a, a ∈ Σ, write down the regular expression for insert(L(r), x)
• Assume r = r1 + r2 and that r1′ and r2′ are regular expressions for insert(L(r1), x) and insert(L(r2), x) respectively. Write a regular expression for insert(L(r), x) terms of r1,r2,r1′,r2′,x (you do not have to use all of these).
• Assume r = r1r2 and that r1′ and r2′ are regular expressions for insert(L(r1),x) and insert(L(r2), x) respectively. Write a regular expression for insert(L(r), x) terms of r1,r2,r1′,r2′,x (you do not have to use all of these).
• Assume r = r1∗ and that r1′ is a regular expression for insert(L(r1), x). Write a regular expression for insert(L(r), x) in terms of r1, r1′ , x (you do not have to use all of these).
Let N1 = (Q1,Σ,δ1,s1,A1) and N2 = (Q2,Σ,δ2,s2,A2) and N3 = (Q3,Σ,δ3,s3,A3) be three NFAs. Let n1, n2, n3 be the number of states in N1, N2, N3 respectively. Describe an NFA N = (Q, Σ, δ, s, A) that accepts the language (L(N1) ∩ L(N2)) ∪ L(N3). For full credit your NFA N should have O(n1n2 + n3) states.
• Give a high-level description of how you can construct N using procedures you have learnt in lecture or homework.
• Give a formal tuple notation for N . That is, you need to explain Q, δ, s, A in terms of the parameters of N1, N2, N3.
CS/ECE 374 Midterm 1 Spring 2021
5 NFAs and Subset Construction
Consider the NFA N shown below.
s 0 q1 1 q2
q3 q4 q5 q6
• Show that 1001 is accepted by N by describing an accepting walk in the NFA.
• Whatisδ∗(s,ε)?
• What is the ε-closure of {q3, q5}?
• Consider the subset construction to create a DFA M = (Q′,Σ,δ′,s′,A′) from N. What is
δ′(X , 0) where X = {q1, q2}?
• Argue that 100 is not accepted by N by computing δ∗(s,100).
6 Non-regularity
Prove that the language L = {03n | n ≥ 0} is not regular. You can use any proof technique you want. If you describe a fooling set for the language you need to justify the validity of the fooling set.
7 Regularity
Given a string w a prefix is any string x such that there is a string y such that x y = w. A proper prefix of w is a string x such that there is y with |y| ≥ 1 such that x y = w. We will call a string x a proper-proper prefix of w if there is a string y such that |y| ≥ 2 and x y = w. If w = abcde then abc, ab, a, and ε are proper-proper prefixes of w. For a language L we define the language
PPPREFIX(L) = {x | x is proper-proper prefix of some string w ∈ L} PPPREFIX(L) = {x | ∃y,|y| ≥ 2, x y ∈ L}.
Alternatively,
Suppose L is regular. Prove that PPPREFIX(L) is regular. In particular, given a DFA M =
(Q,Σ,δ,s,A) for L describe an NFA N that accepts the language PPPREFIX(L(M)).
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com