CS/ECE 374 Midterm 1 Solutions 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
Copyright By PowCoder代写 加微信 powcoder
• L2 ={w∈{0,1}∗ |all0blocksofwareofevenlength}. Recalla0blockisamaximal
non-empty subtring of 0’s in the string. The string 0000100 is in L2 but not 001110. Briefly explain your regular expressions.
L1: (0 + 10 + 110)∗(ε + 1 + 11) We cannot have more than two 1s appear without immediately following with a 0 or the end of the string. This is the same as Lab 11⁄2
Problem 2, except excluding 111 instead of 000.
L2: (00 + 1)∗ The term 00 only allows an even number of 0s at a time.
Rubric: 10 points: 5 points for each part.
• 1 points for a brief English explanation of your regular expression. This is how you argue that
your regular expression is correct.
– For longer expressions, you should explain each of the major components of your expres-
sion, and separately explain how those components fit together.
– We do not want a transcription; don’t just translate the regular-expression notation into
• 4 points for correctness.
– -1 for a single mistake: one typo, excluding exactly one string in the target language, or including exactly one string not in the target language.
– -2 for incorrectly including/excluding more than one but a finite number of strings.
– -4 for incorrectly including/excluding an infinite number of strings.
• Regular expressions that are more complex than necessary may be penalized. Regular expres- sions that are significantly too complex may get no credit at all. On the other hand, minimal
regular expressions are not required for full credit.
CS/ECE 374 Midterm 1 Solutions Spring 2021
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.
Solution: L is the intersection of the languages L1 = w ∈ {0, 1}∗ w ends in 10 and L2 = w ∈ {0, 1}∗ |w| is odd.
Here is a DFA M1 for L1. This is the same DFA seen in Homework 1 Problem 2 solutions. 01
ε 1 1 0 10
• The state ε means no symbols have been read yet, only 0 has been read, or the last two symbols read were 00
• The state 1 means the last symbol read was 1
• The state 10 means the last two symbols read were 10
Equivalently, the state labeled x corresponds to the maximal prefix of 10 seen in the (up
to) two most recently read symbols. Here is a DFA M2 for L2:
• The state Even means that we have read an even number of characters
• The state Odd means that we have read an odd number of characters
Finally, the DFA M for L can be built by applying the product construction to M1 and M2. Note that the positions of the states have been rearranged to reduce edge crossings.
CS/ECE 374 Midterm 1 Solutions Spring 2021
Rubric: 10 points. Standard DFA design rubric.
• 2 points for an unambiguous description of a DFA, including the states set Q, the start state s,
the accepting states A, and the transition function δ.
– Drawings: Use an arrow from nowhere to indicate s, and doubled circles to indicate
accepting states A. If A = ∅, say so explicitly. If your drawing omits a junk/trash/reject state, say so explicitly. Draw neatly! If we can’t read your solution, we can’t give you credit for it.
– Text descriptions: You can describe the transition function either using a 2d array, using mathematical notation, or using an algorithm.
– Product constructions: You must give a complete description of each the DFAs you are combining (as either drawings, text, or recursive products), together with the accepting states of the product DFA.
• 2 points for briefly explaining the purpose of each state in English. This is how you argue that your DFA is correct.
– For product constructions, explaining the states in the factor DFAs is both necessary and sufficient.
• 6 points for correctness.
– −1 for a single mistake: a single misdirected transition, a single missing or extra accepting
state, rejecting exactly one string that should be accepted, or accepting exactly one
string that should be accepted.
– −3 for incorrectly accepting/rejecting more than one but a finite number of strings.
– −6 for incorrectly accepting/rejecting an infinite number of strings.
• DFAs that are more complex than necessary may be penalized. DFAs that are significantly more complex than necessary may get no credit at all. On the other hand, minimal DFAs are not required for full credit, unless the problem explicitly asks for them.
• Half credit for describing an NFA when the problem asks for a DFA.
CS/ECE 374 Midterm 1 Solutions Spring 2021
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).
• Base cases:
– For r = ∅, insert(∅, x) = ∅, so the regular expression is ∅
– For r = ε, insert({ε}, x) = {x}, so the regular expression is x
– For r = a, insert({a}, x) = {ax, xa}, so the regular expression is ax + xa • insert(L(r1+r2),x)=insert(L(r1)∪L(r2),x)={uxv|uv∈L(r1)∪L(r2)}
= {ux v | uv ∈ L(r1)} ∪ {ux v | uv ∈ L(r2)} = insert(L(r1), x) ∪ insert(L(r2), x), so the regular expression for insert(L(r1 + r2), x) is r1′ + r2′
• Assume r1 and r2 are not ∅, otherwise r = ∅. We can insert x inside of L(r1), inside of L(r2), or between two strings from each language. In summary, the regular expression
for insert(L(r1r2),x) is r1′r2 +r1xr2 +r1r2′ r1′r2 and r1r2′ allow for inserting x at
the end of r1 and the beginning of r2, respectively, so the r1xr2 term is redundant. • Assume r1 ̸= ∅, otherwise r1∗ = ε. We can insert x inside of some instance of L(r1), or between two instances of L(r1). In summary, the regular expression for insert(L(r1∗), x)
is r1∗(r1′ + x)r1∗ Unlike the previous case, the +x term is not redundant: we must
allow for the possibility of inserting x when r1∗ produces ε. Accordingly, r1∗ r1′ r1∗ + x
is an equivalent expression for insert(L(r1∗), x).
Rubric: 10 points.
• 1 point for syntactically correct regular expressions in all parts.
• 1 point for each correct base case (all or nothing).
• 2 points for each correct recursive case. Minimal regular expressions are not required.
– For the last part, half credit for missing +x somewhere. All or nothing for all other parts.
CS/ECE 374 Midterm 1 Solutions Spring 2021
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.
• We can apply the product construction for intersection from Homework 2 Problem 3 to N1 and N2 to obtain an NFA N12 for L(N1) ∩ L(N2). Then we can apply the construction for union in Thompson’s algorithm to N12 and N3 to obtain the desired NFA N for (L(N1) ∩ L(N2)) ∪ L(N3).
• Below we assume that (Q1 × Q2) ∩ Q3 = ∅, so that we do not accidentally combine states in the definition of Q. We introduce a new starting state s′ with ε transitions to the starting states of N12 and N3. The transitions for (q1,q2) ∈ Q1 ×Q2 are lifted directly from Homework 2 Problem 3 solutions. To simplify the construction slightly, we will ignore the requirement in Thompson’s algorithm of having exactly one accepting state.
Q := s′ ∪ Q1 × Q2 ∪ Q3 s := s′
A:=(A1 ×A2)∪A3 δ(s′, ε) := {(s1, s2), s3}
For(q1,q2)∈Q1×Q2,a∈Σ, δ((q1,q2),a):=δ1(q1,a)×δ2(q2,a) For(q1,q2)∈Q1×Q2, δ((q1,q2),ε):=δ1(q1,ε)×{q2}∪{q1}×δ2(q2,ε)
For q3 ∈ Q3, δ(q3, a) := δ3(q3, a)
Rubric: 10 points: 5 points for each part.
• Full points for any correct high-level description of the construction that results in O(n1n2 + n3)
– Partial credit: 2 points for a correct construction with ω(n1n2 + n3) states.
• 5 points for correctly (formally) describing an NFA. Do not penalize for overly large NFAs; we already did that in the previous part.
– +2.5 for accepting all strings in the target language
– +2.5 for accepting only strings in the target language
– −1 for a single mistake in the formal description (for example a typo)
– Double-check correctness when the input language is ∅, or ε, or 0∗, or Σ∗.
CS/ECE 374 Midterm 1 Solutions 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).
• Onepossibility: s−→q3 −→q4 −→q5 −→q2 −→s−→q1 −→q2,whereq2 isan
accepting state.
Another possibility: s −→ q5 −→ q6 −→ q2 −→ s −→ q1 −→ q2, where q2 is an
accepting state.
• {s,q2,q3,q5}
• {s,q2,q3,q5}
• δ∗(s, 100) = {q1}, which does not contain any accepting states.
Rubric: 10 points. 2 points for each part (all or nothing).
CS/ECE 374 Midterm 1 Solutions Spring 2021
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.
Solution: Following the idea for the language 02n n ≥ 0:
LetF=L=03n n≥0.
Let x and y be arbitrary elements of F.
Thenx=0 andy=0 fornon-negativeintegersiandjwherei̸=j.
2i 2i+1 n≥0 ,wesetz=0 ,sothatxz=0
yz=03j02·3i =03j+2·3i ∈/Lsincei̸=j.
Thus F is an infinite fooling set for L, so L cannot be regular.
2n For 0
.Theanalogoussituationherewould
. Toachievethis: Letz=0
Thenxz=03i02·3i =03·3i =03i+1 ∈L,and
Rubric: 10 points. Standard fooling set rubric: • 4 points for the fooling set:
– +2 for explicitly describing the proposed fooling set F.
– +2 if the proposed set F is actually a fooling set for the target – No credit for the proof if the proposed set is not a fooling set. – No credit for the problem if the proposed set is finite.
• 6 points for the proof:
– The proof must correctly consider arbitrary strings x, y ∈ F.
* No credit for the proof unless both x and y are always in F.
* No credit for the proof unless x and y can be any strings in F. – +2 for correctly describing a suffix z that distinguishes x and y.
– +2forprovingeither xz∈Lor yz∈L
– +2 for proving either yz ∈/ L or xz ∈/ L, respectively.
CS/ECE 374 Midterm 1 Solutions Spring 2021
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
Alternatively,
PPPREFIX(L) = {x | x is proper-proper prefix of some string w ∈ L} PPPREFIX(L) = {x | ∃y,|y| ≥ 2, x y ∈ L}.
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)).
Solution: We will think of PPPREFIX(L) as the set of strings obtained by deleting a string of length at least two from the end of a string in L. Following the examples of the various delete problems seen before, we will simulate reading in the input, and then guessing transitions corresponding to reading a string of length at least two.
For each q ∈ Q, let Xq ⊆ Q be the set of states of M that can be reached from q by following two or more transitions. Equivalently, Xq = {δ∗(q, y) | y ∈ Σ∗ such that |y| ≥ 2}. We will create two copies of M labeled Before and After. For each q ∈ Q, add ε-transitions from the Before copy of q to the After copies of the elements of Xq. The After copy has no transitions, and we accept only if we land on a copy of an accepting state.
Intuitively, the NFA reads some amount of the input to get to some state (q, Before), and then guesses some string y of length at least 2 and takes an ε-transition to (δ∗(q, y),After).
Formally, we create an NFA N = (Q′, Σ, δ′, s′, A′) as follows:
Q′ := Q × {Before, After} s′ := (s, Before)
A′ := {(q,After) | q ∈ A}
{(δ(q, a), Before)} a ∈ Σ
δ′((q,Before),a):= {(δ∗(q,y),After)| y∈Σ∗,|y|≥2}=Xq×{After} a=ε δ′((q, After), a) := ∅
Solution: Recall that for PREFIX(L(M)), one possible solution is to compute a set X consisting of states that can reach an accepting state, and then set X to be the new set of accepting states. We will adapt this idea to solve PPPREFIX.
Let X ⊆ Q be the set of states of M that can reach an accepting state by following a walk of length at least two. Equivalently, X = {q ∈ Q | ∃y,|y| ≥ 2 and δ∗(q, y) ∈ A}.
Observe that δ∗(s, x) ∈ X if and only if there is some string y of length at least two such that δ∗(s, x y) = δ∗(δ∗(s, x), y) ∈ A. So all we need to do is change the set of accepting states to X .
SoinfacttheDFA N=(Q,Σ,δ,s,X) acceptsPPPREFIX(L(M)).
CS/ECE 374 Midterm 1 Solutions Spring 2021
Solution: Notice that PPPREFIX(L) = Reverse(PSuffix(PSuffix(Reverse(L)))). Thus given M, we can apply the construction given in lecture/Jeff’s notes for Reverse, then apply the construction from Homework 2 Problem 2 for PSuffix twice, and finally apply the construction for Reverse once more to obtain an NFA N for PPPREFIX(L). Strictly speaking, the constructions given in lecture/notes and Homework apply to DFAs, not NFAs, but we can run the incremental subset construction in between as necessary to convert the intermediary NFAs into DFAs before feeding them into the next construction.
Rubric: 10 points. Standard langage transformation rubric:
+ 2 for a formal, complete, and unambiguous description of the output automaton, including
the states, the start state, the accepting states, and the transition function, as functions of an arbitrary input DFA.
– No points for the rest of the problem if this is missing.
+ 2 for a brief English explanation of the output automaton. We explicitly do not want a formal
proof of correctness, or an English transcription, but a few sentences explaining how your machine works and justifying its correctness. What is the overall idea? What do the states represent? What is the transition function doing? Why these accepting states?
+ 6 for correctness
– +3 for accepting all strings in the target language
– +3 for accepting only strings in the target language
– −1 for a single mistake in the formal description (for example a typo)
– Double-check correctness when the input language is ∅, or ε, or 0∗, or Σ∗.
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com