SOLUTION SET for ASSIGNMENT 3 Problem 3a.1 [10 pts] _> b ---> e --> g / ___/ \_ a / \ ^\_> c --> d ---> f | | |________/ If you do (search 'a 'f), you might wind up in in an infinite loop; specifically, if you push the arc (d a) onto the stack before the arc (d f), you'll go through the sequence of states a-c-d-a-c... forever. Problem 3a.2 [20 pts: 15 pts for program, 5 pts for execution traces] (defun search (start-node target) (do ((possibilities (list start-node)) (current-node) (visited)) ;; <== ADDED THIS VARIABLE DECLARATION ;; If the possibilities list is empty, we didn't find the target. ((null possibilities) 'FAILURE) ;; WHAT TO DO REPEATEDLY WHILE EXECUTING THE LOOP (format t "~%~%Current possibilities: ~S, " possibilities) (setf current-node (pop possibilities)) (push current-node visited) ;; <== ADDED RECORD-KEEPING ;; If we've found the target, break out of the loop and accept. (format t " now exploring node ~A" current-node) (if (eq current-node target) (return 'SUCCESS)) (dolist (pair (get-outward-edges current-node)) (if (not (member (second pair) visited)) <== ADDED THIS 'IF' (push (second pair) possibilities))))) * (search 'a 'f) Current possibilities: (A), now exploring node A Current possibilities: (B C), now exploring node B Current possibilities: (E C), now exploring node E Current possibilities: (G C), now exploring node G Current possibilities: (C), now exploring node C Current possibilities: (D), now exploring node D Current possibilities: (F), now exploring node F SUCCESS * (search 'c 'a) Current possibilities: (C), now exploring node C Current possibilities: (E D), now exploring node E Current possibilities: (G D), now exploring node G Current possibilities: (D), now exploring node D Current possibilities: (A F), now exploring node A SUCCESS Problem 3.b.1: [5 pts: 3 for loop, 2 pts for not consuming any input] This same problem can appear when simulating an NDFA that permits a loop without consuming any input. Problem 3.b.2 [10 pts] Lines with modifications indicated by "<==" ---------------------------------------------------------------- Algorithm for simulating an NDFA, that protects against cycles ---------------------------------------------------------------- Given an NDFA, M, consisting of , and a string of input symbols, S: set current-state to Initial(M) set input-length to length(S) set possibilities to singleton list ([current-state,1]) set visited-configs to singleton list ([current-state,1]) <== ADDED while possibilities is not empty { set [state,loc] to pop(possibilities) if (state is a member of Final(M) AND loc == input-length + 1) Accept and terminate set input-symbol to the Nth symbol of S (numbering from 1) set transitions to the list of Transitions(M) departing state on input-symbol for each transition in transitions { if symbol is EPSILON and [destination,loc] is not on visited-configs <== ADDED add configuration [destination,loc] to possibilities else if [destination,loc+1] is not on visited-configs <== ADDED add configuration [destination,loc+1] to possibilities } } Reject and terminate Problem 3.c.1 (Allen, Ch 3, Problem 10) [15 pts, 5 each] a. The RTN but not the CFG allows ZERO OR MULTIPLE ADJECTIVES in an NP, e.g. "the big brown dog in the yard". The RTN but not the CFG allows an NP with NO PREPOSITIONAL PHRASE, e.g. "the big dog". b. A CFG (weakly) equivalent to the RTN is as follows: NP -> art NP1 NP -> art NP1 PPS NP1 -> adj NP1 NP1 -> N PPS -> PP PPS PPS -> PP PP -> prep NP Notice that the "zero or more PP's" behavior is done by making PP optional within the NP (allowing zero of them) and getting "one or more PP's" using recursion on PPS Getting "zero or more adjectives" is done by having NP1 be a constituent that can go to either N alone (zero adjectives) or an adjective followed by NP1 recursively (one or more adjectives). c. An RTN (weakly) equivalent to the CFG is as follows: art PUSH NP1 pop NP: >(q0) -----> (q1) ----------> (q2) -----> adj noun PUSH PPS pop NP1: >(q3) -----> (q4) ----------> (q5) ---------> (q6) -----> prep PUSH NP pop PPS: >(q7) -----> (q8) ----------> (q9) -----> ^ |_____________________________/ JUMP This solution eliminates the tail recursion in the PPS rule of the grammar, replacing it with a loop. You could also have made a more direct translation of the two rules: PUSH PP PUSH PPS pop PPS: >(q7) -------> (q8) ----------> (q9) -----> prep PUSH NP pop PP: >(q10) -------> (q11) ----------> (q12) -----> There are various other correct solutions, e.g. you could have combined what I've written as the NP and NP1 networks into a single network, etc. Problem 3.c.2 [10 pts] S -> NP VP NP -> NP PP NP -> DET N VP -> V NP VP -> V PP -> P NP DET -> a | the N -> man | dog | house | telescope | spoon VP -> saw | fed | barked P -> with 1 2 3 4 5 6 the man fed the dog Operation Stack Input-location start () 1 shift (the) 2 reduce (DET) 2 shift (man DET) 3 reduce (N DET) 3 reduce (NP) 3 shift (fed NP) 4 reduce (V NP) 4 shift (the V NP) 5 reduce (DET V NP) 5 shift (dog DET V NP) 6 reduce (N DET V NP) 6 reduce (NP V NP) 6 reduce (VP NP) 6 reduce (S) 6 ACCEPT It's also ok if you did the "shift" operation by shifting in a pre-terminal (e.g. Det) when you saw a terminal symbol in the input (e.g. "the"). In that case, for example, the first "shift" operation would have resulted directly in a stack containing (DET) rather than having to do a shift and then a reduce. Problem 3.c.3 [15 pts] (i) Top-down parse 1 2 3 4 5 6 the man fed the dog Operation Stack Input-location start (S) 1 expand (NP VP) 1 expand (DET N VP) 1 expand (the N VP) 1 match (N VP) 2 expand (man VP) 2 match (VP) 3 expand (V NP) 3 expand (fed NP) 3 match (NP) 4 expand (DET N) 4 expand (the N) 4 match (N) 5 expand (dog) 5 match () 6 ACCEPT It's also ok if you did the "match" operation by matching a preterminal on the stack (e.g. Det) with a terminal symbol in the input buffer (e.g. "the") rather than expanding all the way down to terminal symbols. (ii) The parser would go into an infinite loop, continuing to expand NP into NP PP over and over again. In general, left-recursive rules (rules of the form "X -> X alpha") cause this problem for top-down parsers. (iii) This is not a problem for bottom-up parsers because they are driven by the input: they never predict or propose a constituent unless they have evidence for it. Problem 3.c.4 [15 points, one for each correct cell in rows 2-6] 1 2 3 4 5 6 1 { A } { B } { B } { A } { B } { A } 2 { S } { A } { A } { S } { A } 3 { B } { A B } { S } { B } 4 { B S A } { S A } { A B } 5 { S B A } { A S B } 6 { B S A } Yes, the string is in L(G), since S is in cell [1,6].