CSC 520 Spring 2021
Midterm #1
125 points
Answer sheet
1. (45 points) ∑={a,b}, L = {s: s starts with ab, ends with ba, and #a(w) > #b(w)}. For
example, aba³b²ab²a ∈ L; s = abba ∉ L because #a(s) = #b(s); t = abaab ∉ L because t
does not end with ba. Prove that L ∉ RLs using the RL pumping theorem. Define w in
terms of k, the pumping length, and remember that the only valid assumption about k is
that k ≥ 1. Deriving formulas for x and z would waste your time, so please just
concentrate on y.
1. Let w = abaᵏbᵏa. Then w ∈ L and |w| ≥ k, so w can be considered as the
concatenation of 3 substrings xyz, to which the 3 pumping theorem guarantees apply:
i. |xy| ≤ k
ii. y ≠ ℇ
iii. ∃y(∀q(w' = xyqz, q≥ 0, and w' ∈ L). In other words, there is some substring y in the
first k characters of w that can always be pumped out, or in any number of times, and
the resulting string w' will also be in L.
2. Assume that guarantees i and ii are true, and show that guarantee iii is false by
proving that:
∀y(∃q(w=xyz, w' = xyqz, q≥ 0, and w' ∉ L)
Case 1: y contains either or both of the inital symbols ab. Let w' = xy⁰z (pump
out). Then w' ∉ L because instead of starting with ab, it starts with either aa (if
the b in the 2nd position was removed) or ba (if y was the initial a).
Case 2: y consists of 1 to k-2 symbols in the 2nd a region. Let w' = xy⁰z (pump
out). In terms of k and ∑, w' = abak-|y|bka. #a(w')≤k+1=#b(w'), and w' ∉ L
because it does not have more a's than b's.
3. y cannot contain any symbols to the right of the second a region, because that would
violate the guarantee that |xy| ≤ k.
∴ L ∉ RLs, because we have shown that ∀y(∃q(w=xyz, w' = xyqz, q≥ 0, and w' ∉ L). In
other words, for all possible values of y, there is some way to pump w to generate w' ∉
L.
CSC 520 Spring 2021 Midterm #1 1
2. (40 points) Modify the file Func_headers.py, available on iLearn, so that the program shows
function headers it detects in an input file. The most important change you will need to make is
to func_header_regex, so that in addition to matching function headers with single parameters:
It allows that single parameter to take a default value of an integer, a string, or a variable.
It captures the function header match in a group, excluding leading and trailing white
space.
You must also change Match_func_header, so that it returns the matched header without the
enclosing white space. Match_func_header must still return None if there is no match. Here are
some examples of matched and unmatched lines:
This code would work
import re
# '$' isn't allowed in Python variable names
#Python variable names must start with a letter or ...
start_var_chars = '[a-zA-Z_]'
#... but digits are also allowed in trailing chacters
trail_var_chars = '[a-zA-Z0-9_]'
var_chars = start_var_chars + trail_var_chars + '*'
func_header_regex =\
re.compile(fr'''^\s* # any and all blanks & tabs at start of string
(def\s+ # start group, "def" then blanks & tabs
{var_chars} # function name
\s*\(\s* # blanks & tabs, '(', blanks & tabs
{var_chars} #parameter name
\s* # blanks & tabs
(?:\s*=\s* # start non-capture, =
(?:\d+|'.*'|".*"|{var_chars}))?
\)
\s*:)\s*$ # blanks & tabs, :, end group, end string
''', re.VERBOSE)
def Match_func_header(text):
m = func_header_regex.search(text)
if m != None:
return m.group(1)
return None
Matched lines Unmatched lines
def f(a): def f():
def f (a) : def 1f(a):
def f12_(a5b): def f12_(a5b)
def f(a=12): def f(a=3.14):
def f(a=-12): def f(a=12-):
def f(a='hello world'): def f('hello world'):
def f(a="test"): def f(a="test):
def f(a=fileName): def f(a=2fileName):
CSC 520 Spring 2021 Midterm #1 2

if __name__ == '__main__':
o = open('func_headers.out','w')
while True:
filename = input('Enter file to check for function headers, or enter to
quit: ')
if filename == '': break
try:
f = open(filename, 'r')
except:
print(f'Could not open "{filename}" for reading')
continue
print(f'Looking for function headers in "{filename}" …', file=o)
lineNum = 1
for line in f.readlines():
m = Match_func_header(line)
if m:
pfx = 'Python function header on line'
print(f'{pfx} {lineNum}: "{m}"', file=o)
else:
pfx = 'No Python function header on line'
print(f'{pfx} {lineNum}: "{line[:-1]}"', file=o)

lineNum += 1
print(f'… "{filename}" function header search complete\n', file=o)
f.close()
print('Function header detection testing complete.')
o.close()

CSC 520 Spring 2021 Midterm #1 3
3. (40 points) ∑={a,b}, L={w : w starts with ab, ends with ba, #a(w)%2=0, and #b(w)%2=1}.
For example, abbba ∈ L; abababa ∈ L; aba ∈ L; w = baa ∉ L both because w does not start with
ab, and because w does not end with ba; w = abba ∉ L because #b(w)%2=0; and w = ababba ∉
L because #a(w)%2=1. Use JFLAP to create an FSM that accepts L. Submit your answer as
a .jff file.

CSC 520 Spring 2021 Midterm #1 4

































































































































































































































学霸联盟