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