The goals of this lab are to:
This assignment consists of a written homework portion and a programming portion. Write your written solution using LATEX. A python sketch of the programming portion has been provided, but you are free to write a solution in C, C++, Java, or Python if desired. Submit both portions using github. This is a partnered assignment. You may work with one partner and submit a joint assignment. It is OK to discuss approaches at a high level with other students that are not your partner, but you must do your own write-up. Do not share your write up with other groups, and do not read other group's solutions. Please refer to the syllabus or ask me if you have questions about the policy.
cd ~/cs46 git clone git@github.swarthmore.edu:CS46-S18/lab06-<group>.git ./lab06where <group> is your group name. It is probably best to just log into github and find your repo name there.
Given a grammar G in Chomsky Normal Form, and an input string w=w1w2⋯wn, we can design a polynomial time algorithm to determine if w∈L(G). The basic idea is to compute for all substrings x=wi⋯wj,j≥i of w if there is some rule in G that generates x. Define Vi,j to be the set of all variables in V∈G that that can derive substring x=wi⋯wj. G can derive w if V1,n contains the start symbol S∈V
Our algorithm for parsing strings computes the sets Vi,j for 1≤i≤n,j≥i. The algorithm proceeds in a series of rounds, where in each round, it considers substrings of length s,1≤s≤n. In the first round, the algorithm sets Vi,i to {A∈V,A→wi for some rule A in the grammar }.
For substrings longer than 1, the algorithm checks if the substring x=xi⋯xi+s−1 can be broken into two smaller pieces at some index k, y=xi⋯xk and z=xk+1⋯xi+s−1 such that there is a rule A→BC in the grammar where B∈Vi,k and C∈Vk+1,i+s−1. If such a rule A exists, we add A to Vi,i+s−1.
After finishing all rounds, we just need to check if S∈V1,n. A pseudocode summary is below
for i in 1 to n: Add A to V[i,i] if A yields w[i] is a rule for s in 1 to n-1: for i in 1 to n-s: for k in i to i+s-1: if A yields BC is a rule where B is in V[i,k] and C is in V[k+1,i+s] then add A to V[i,i+s] return True if S is in V[1,n]Some example output for a CNF grammar for anbn.
$ cat grammar1.txt a b S: E S: A1 B S: A B A1: A S A: a B: b $ python cnf.py grammar1.txt string1.txt
abab: False a: False aaaabbbb: True ab: TrueFor the balanced parens
$ cat grammar2.txt ( ) S: E S: A1 B S: A B S: S S A1: A S A: ( B: ) $ python cnf.py grammar2.txt string2.txt
(): True E: True ()(): True (()()): True )(: False (((()): False
The grammar format starts with a line containing the symbols of the alphabet separated by spaces, a blank line, and then the grammar rules. The first rule lists the start symbol on the left hand side. The rule format is V: A B to indicate the rule V→AB. Note A1 is a single variable not two variables. Variables on the right hand side are separated by spaces.
self.start = "S" #set start variable result = self.matchedSym("a") # call the matchedSym method with argument 'a' # result is saved in local variable result.
d = {} # create empty dictionary i=1 j=2 #store the value 1 in the dictionary with the key (1,2) d[(i,j)] = 1 #print the value associated with a key (i,j) #if the key does not already exists, it will throw an error print(d[(i,j)]) """ you can store any object as a value. A list may be handy. Python dictionary keys must be immutable, so a tuple (i,j) is fine, but a list [i,j] is not a valid key. """
if "a" in "apple": print("Yes!")
#print 1 through 9 inclusive for i in range(1,10): print(i)If i is ommited from the range() function, it is assumed to be 0.
If you have questions about the existing code structure in cnf.py, please ask in lab or on Piazza. I don't want you to be spending hours deciphering python syntax.
Once you have edited the files, you should publish your changes using the following steps:
$ git add hw06.tex Readme.md cnf.py $ git commit -m "completed lab06" $ git push
If you make changes to files after your push and want to share these changes, repeat the add, commit, push loop again to update the github server.
To recap, the git commit cycle is git add, git commit, git push. Don't forget to git push when you have completed an assignment.
You can review the basic git commands on the github help pages. Eventually, you should get in the habit of using git status to see if everything has been published, but we will talk about this more throughout the semester.
Remember to add, commit, push. You may commit and push as often as you like, and only the most recent push will be graded.