Modify the Scheme program of Figure 11.1 or the OCaml program of Figure 11.3 to simulate an

Question:

Modify the Scheme program of Figure 11.1 or the OCaml program of Figure 11.3 to simulate an NFA (nondeterministic finite automaton), rather than a DFA. (The distinction between these automata is described in Section 2.2.1.) Since you cannot “guess” correctly in the face of a multivalued transition function, you will need either to use explicitly coded backtracking to search for an accepting series ofmoves (if there is one), or keep track of all possible states that the machine could be in at a given point in time.

Figure 11.1

(define simulate (lambda (dfa input) (letrec ((helper ; note that helper is tail recursive, ; but builds the list of moves in reverse order (lambda (moves d2 i) (let ((c (current-state d2))) (if (null? i) (cons c moves) (helper (cons c moves) (move d2 (car i)) (cdr i))))))) (let ((moves

Figure 11.3

Fantastic news! We've Found the answer you've been seeking!

Step by Step Answer:

Related Book For  book-img-for-question
Question Posted: