final-proj
Final Project: Concept Roundup¶
csc427, semester 232
university of miami
copyright (c) 2023 burton rosenberg. All rights reserved.
This is the Final Exam for CSC427-232, distributed on Wednesday, 3 May 2023, and due before midnight of Monday, 8 May. There are no make ups or lateness for this exam.
Honor Code Signature Required: I am have read the University of Miami Honor Code and accept its terms. My signature here reaffirms that pledge. Please replace the empty string below with your name. ☟✐
I, the signer, attest:, that I have neither to given or received assistance or advice for the performance of this Final Examination.
sign_the_honor_code_with_your_name_in_the_following_string = “”
def assert_honor_code():
assert len(sign_the_honor_code_with_your_name_in_the_following_string)>0, “Honor Code not signed.”
assert_honor_code()
from final_proj_util import *
Problem A: NP completeness and reductions¶
Reduce 3SAT to k-Vertex cover.
Graph Representation¶
A graph is represented by the Graph class where the n vertices of the graph are numbered 0 through n-1
self.e is a list of integer pairs, where pair (i,j) represents and edge from vertex i to vertex j.
The graph is undirected, so that edge (i,j) implies edge (j,i).
self.v[i] is the label of the i-th vertex. these labels can be useful in guiding the reduction.
k-Vertex Cover¶
in the following Graph class, complete the methods,
is_cover, given a list of vertices but their integer values (not the lables) returns True if these
vertices cover the edges.
has_k_cover: given a k, applies is_cover to all k sized subsets of the vertices and returns True if
is_cover ever returns True.
count_k_cover: given a k, applies is_cover all all k sized subsets of the vertices and creates a list
of all subsets for which is_cover is True.
In the following Reduce3SatVertexCover complete the code so that the object builds an object of type
Graph according to the 3SAT to Vertex Cover as described in the textbook.
The methods are only a suggestion as to how to break down the work into pieces, following the description in the textbook.
import itertools
class Graph:
def __init__(self,vertices,edges,verbose=False):
self.v = vertices[:] # a list of labels, self.v[i] label for vertex i
self.e = set(edges) # a list of pairs, e.g. (1,2) is an edge between vertex 1 and 2
self.verbose = verbose
def __repr__(self):
return f’v: {self.v}\ne: {self.e}\n’
def is_edge(self,e):
# because undirected try both orderings
return (e in self.e) or ((e[1],e[0]) in self.e)
def is_cover(self,cover):
# returns True if cover is a cover, else return False
# Cover is a list of vertices identified as integer
### code here
return None
def has_k_cover(self,k):
# returns True if there is a vertex cover of size k, else return False
# k is in integer
### code here
return None
def count_k_cover(self,k):
# returns a list of k covers
# k is an integer
covers = []
### code here
return covers
class Reduce3SatVertexCover:
def __init__(self,cnf_obj,verbose=False):
self.verbose = verbose
self.cnf = cnf_obj
self.var_v, self.var_e = self.make_variable_widget()
self.clause_v, self.clause_e = self.make_clause_widget()
e = self.make_connector_edges()
self.graph = Graph(self.var_v+self.clause_v, self.var_e+self.clause_e+e)
def __repr__(self):
return f’cnf: {self.cnf}\ngraph: {self.graph}’
def get_graph(self):
return self.graph
def make_variable_widget(self):
v, e = [], []
### code here
if self.verbose: print(f’make_variable_widget: {v,e}’)
return (v,e)
def make_clause_widget(self):
v, e = [], []
#### code here
print(f’make_clause_widge: {v,e}’)
return (v,e)
def make_connector_edges(self):
### code here
if self.verbose: print(f’make_connector_edgse: {e}’)
Example test for Problem A¶
fig_7_33 = [[(‘x1’,True),(‘x1’,True),(‘x2’,True),],
[(‘x1’,False),(‘x2’,False),(‘x2’,False),],
[(‘x1’,False),(‘x2’,True),(‘x2’,True),],]
# a typical output is:
all 8-covers:
[(1, 2, 4, 5, 8, 9, 10, 11), (1, 2, 4, 5, 8, 9, 10, 12), (1, 2, 4, 5, 8, 9, 11, 12)]
all satisfying assignments for (x1 OR x1 OR x2) AND (~x1 OR ~x2 OR ~x2) AND (~x1 OR x2 OR x2):
[{‘x1’: False, ‘x2′: True}]
# but your milage may vary
cnf_obj = CnfFormula(fig_7_33)
red = Reduce3SatVertexCover(cnf_obj,verbose=False)
print(f’all {k}-covers:\n\t{red.graph.count_k_cover(k)}’)
print(f’all satisfying assignments for {cnf_obj}:\n\t{cnf_obj.count_sat()}’)
Problem B: Context Free Grammers in Chomsky Normal Form¶
You are to write context free grammars for the following languages. The grammars must be in proper chomsky normal form.
a*, the string of all a’s including the empty string
ab, the string of some a’s, including none, followed by some b’s, including none.
a^i b^i, the string of a’s followed by b’s, with the same number of each.
w w^R over {x,y}. An even length string of x’s and y’s,the second half is the first half reversed.
a^i c^j b^i, the string of some a’s followed by some c’s followed by some b’s, with the same number of a’s as b’s, and any number of c’s, including none.
Representation¶
The : character is the empty string. It can only be allowed in the rule startstate->:.
The grammar is presented as a dictionary of lists. The key is the variable (non-terminal), and the list is a list of right hand sides for the rule. Take care of the form: each must either be a single character which is not a non-terminal, or two characters each of which is a non-terminal
A dictionary is given for the example of a simple finite language.
# example. The language {”,’a’,’bb’,’bab’}
startstate_example = ‘S’
grammar_example = {
startstate_example:[‘:’,’a’,’BB’,’BX’],
‘B’:[‘b’],
‘A’:[‘a’],
‘X’:[‘AB’]
startstate_astar = ‘S’
grammar_astar = {
startstate_astar:[], # more in the list
### more rules here
startstate_astarbstar = ‘S’
grammar_astarbstar = {
startstate_astarbstar:[], # more in the list
### more rules here
startstate_aibi = ‘S’
grammar_aibi = {
startstate_aibi:[], # more in the list
### more rules here
# w w^R , w in {x,y}*
startstate_wwr = ‘S’
grammar_wwr = {
startstate_wwr:[], # more in the list
### more rules here
# a^i c^j b^i
startstate_aicjbi = ‘S’
grammar_aicjbi = {
startstate_aicjbi:[], # more in the list
### more rules here
Example test for Problem B¶
def cnf_cfg_test(t_v):
def check_grammar(grammar,startstate):
for key,value in grammar.items():
for v in value:
if ‘:’ in v:
t = (v==’:’) and (key==startstate)
assert t, f’not allowed: {key}->{v}’
total = (0,0)
for (name,grammar,startstate,trues,falses) in t_v:
print(f’testing {name}’)
check_grammar(grammar,startstate)
cyk = CYK(grammar, startstate)
correct, incorrect = 0, 0
for t in trues:
res = cyk.checkWord(t)
correct += 1
incorrect += 1
print(f’\t{t}: {cyk.checkWord(t)}’)
for t in falses:
res = cyk.checkWord(t)
incorrect += 1
correct += 1
print(f’\t{t}: {cyk.checkWord(t)}’)
total = (total[0]+correct,total[1]+incorrect)
return total
t_v.append((‘a*’,grammar_astar,startstate_astar,[‘:’,’a’,’aa’,’aaaa’],[‘ab’] ))
t_v.append((‘a*b*’,grammar_astarbstar,startstate_astarbstar,
[‘:’,’a’,’aa’,’aaaa’,’ab’,’b’,’bb’,’bbb’,’aabb’,’abb’,’aab’, ],
t_v.append((‘a^i b^i’,grammar_aibi,startstate_aibi,
[‘:’,’ab’,’aabb’,’aaabbb’,],
[‘a’,’aa’,’aaaa’,’ba’,’b’,’bb’,’bbb’,’abb’,’aab’, ‘aaabbbb’]))
t_v.append((‘w w^R’,grammar_wwr,startstate_wwr,
[‘:’,’xx’,’yy’,’xyyx’,’xxyyxx’,’xyxxyx’],
[‘x’,’y’,’xy’,’yx’,’xxxxxy’]))
t_v.append((‘a^i c^j b^i’,grammar_aicjbi,startstate_aicjbi,
[‘:’,’ab’,’aabb’,’aaabbb’,’c’,’cccc’,’acb’,’aaccbb’,’aaacbbb’],
[‘a’,’aa’,’ac’,’ba’,’b’,’bb’,’cbbb’,’abb’,’aab’, ‘aaacccbbbb’]))
t_example = [(‘example’,grammar_example,startstate_example,[‘:’,’a’,’bb’,’bab’],[‘b’,’aaa’])]
cnf_cfg_test(t_example)
cnf_cfg_test(t_v)
Problem C: Multitape Turing Machines¶
Write a Turing Machine that given a strictly positive integer n, halts with the n-th fibonnaci number alone on its tape. The first Fibonacci number is 1, the second is 1, the third is 2, the fourth is 3, etc.
Numbers will be represented in binary, reversed (as in our previous exercises) with the & at the left-hand side, with “trailing zeros” allowed. That is, the number 6 is &011 or &01100.
So the machine started with,
on the first tape halts with,
on the first tape. The content of the other tapes on halting does not matter. Nor does where the heads are at halting.
Hint: This requires a loop. Where there is a loop, there is a loop invariant. A sample loop invariant might be: at the top the loop the three tapes contain,
Where n is the current count (decremented by one and checked for zero to determine whether to leave the loop); f and g are two consecutive Fibonacci numbers (initialized to &0!1) and the third work taped cleaned and end-marked.
Hint: To decrement a number, pretend you are adding the all one’s number to it until a space; then drop the carry out.
from turing_machine_sim import *
mt_fibonacci = “””# &n -> &fn
_ _ _ _ _ _ n n n R
Example test for Problem C¶
def fibonacci_test(tm,steps,verbose=’none’):
for s in [‘&1′,’&01′,’&11′,’&001′,’&101′,’&011′,’&111′]:
res = tm.compute_tm(s,step_limit=steps,verbose=verbose)
if tm.is_exception():
print(f’** exception!’)
return False
if res!=True:
print(f’** reject!’)
return False
print(f'{s}: {tm.get_tape()}’)
return True
# set the number of steps. this helps kill a runaway program.
# I am assuming the program runs in time O(n^2)
steps = 10*(n+5)**2
tm = MachineParser.create_from_description(mt_fibonacci)
fibonacci_test(tm,steps,verbose=’none’)