CSC 520 Spring 2021
Midterm #1
125 points
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
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
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 + '*'
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)
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__':
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
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()
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  