CSCI 320 Foundations of Computer Science 2 Feb 2021
—Midterm #1—
50 marks total, due: Thursday, Feb 4, 11:59 pm
Questions
(1) [12 marks] Given the following DFA state diagram for a machine M , use the algorithm Convert to
obtain an equivalent regular expression that describes the language recognized by M :
1 2
3
b
b
a
a
a
(2) [12 marks] Consider the following regular expression R: (ab)+ ∪ (ba)+b∗.
Give two examples (one mark each, and each less than length 12) of strings that are in the language L
described by R, and two examples of strings (each less than length 12) that are not in the language L.
Create the NFA that recognizes L by building it with the NFA constructions used in the proof that the
regular operations are closed over regular languages from Section 1.2 of the textbook.
(3) Consider the language A of the set of strings over {0, 1} that have only 1’s in the second half, that is,
any 0’s must appear in the first half of a string.
(a) [4 marks] Describe A using set builder notation and length of strings notation (be careful with even
versus odd lengths).
(b) [2 marks] Is the empty string in A?
(c) [8 marks] Prove that A is not regular using an argument by contradiction with the pumping lemma.
CSCI 320 Foundations of Computer Science 2 Feb 2021
(4) For two strings w and s = s1s2 · · · sn over some alphabet Σ let the operation of insertion result in the
set of all strings sw:
{ws, s1ws2 · · · sn, s1s2ws3 · · · sn, s1s2s3ws4 · · · sn, s1s2 · · · sn−1wsn, s1s2 · · · snw}.
Define insertion for two languages L1 and L2 to be
L1〈L2〉 =
⋃
s∈L1 and w∈L2
sw
That is, L2 inserted into L1 is the language of some string in L2 inserted in any position within the
sequence of symbols of some string of L1.
Insertion involving two regular languages always results in a regular language.
(a) [6 marks] Given a DFA M1 that recognizes L1 and a DFA M2 that recognizes L2, give a brief informal
description of an NFA that would prove closure over insertion.
(b) [6 marks] Give a picture describing your NFA similar to Figures 1.46 to 1.48 in Section 1.2.
Submit Instructions
Submit a PDF file of your work together with at most a 10 minute recording explaining your work. Please
submit your PDF file and video to VIULearn > CSCI 320 > Assessment > Assignments > Midterm 1.
If you prefer to write less, and instead give a verbal explanation, use proper terminology covered in Sipser.
At the very least, if it involves any notation, you should write it down.

欢迎咨询51作业君