Finite State Machine in Scheme

I am trying to finish a finite state machine in Scheme. The problem is, that I am not sure how to tell it what characters it should test. If I want to test a String "abc112" then how do I do that?

Here is the code:

#lang racket    
(define (chartest ch)
  (lambda (x) (char=? x ch)))
;; A transition is (list state char!boolean state)
(define fsmtrlst 
  (list
   (list 'start char-alphabetic? 'name)
   (list 'start char-numeric? 'number)
   (list 'start (chartest #\() 'lparen)
   (list 'start (chartest #\)) 'rparen)
   (list 'name char-alphabetic? 'name)
   (list 'name char-numeric? 'name)
   (list 'number char-numeric? 'number)))

(define (find-next-state state ch trl)
  (cond
    [(empty? trl) false]
    [(and (symbol=? state (first (first trl)))
          ((second (first trl)) ch))
     (third (first trl))]
    [else (find-next-state state ch (rest trl))]))

(define fsmfinal '(name number lparen rparen))

(define (run-fsm start trl final input)
  (cond
    [(empty? input)
     (cond
       [(member start final) true]
       [else false])]
    [else
     (local ((define next (find-next-state start (first input) trl)))
       (cond
         [(boolean? next) false]
         [else (run-fsm next trl final (rest input))]))]))

And here is the launch code which I am trying to test:

(fsmtrlst (list 'start (lambda (abc112) (char=? abc112 ))))

EDIT:

ok,.. the overall product is okey, but my tutor is not happy with it,.. he wants me to make a finite state machine with transition function -> something like a global definition which would say: when in state X comes character Y go to Z ... and then i will test a list of characters to see if it is false or true ... So the only difference is that the code shouldn't be specific to use only numbers and letters but any character... is it somehow possible? thank you for your answer

EDIT 2: now I have the basic info how it should look like:

That is, the machine looks like

A ---------> B ----------> C ----------> D ----------> (E) letter number number letter

(define fsmtrlst
 (list
   (list 'A char-alphabetic? 'B)
   (list 'B char-numeric? 'C)
   (list 'C char-numeric? 'D)
   (list 'D char-alphabetic 'E)))

(define fsmfinal '(E))

(define fsmstart 'A)

but i am not sure how to write the definition of fsmstart.

Thank you for answers.

This accepts开发者_如何转开发 sequences of exactly four characters which are letter, number, number, letter, and nothing else.

EDIT 3: I am using tutorials online and a book that my mentor teacher provided. I figured out the fsm I wanted to make. Thank you for your help.

Just out of curiosity:

How would differ to have rather specific fsm?

Example:

START ----"b"-----> STATE A -----"a" ----> STATE B -----"c"-----> FINAL STATE

That the fsm would be true only when the list of characters is "bac" and nothing else. Is it possible?

Thank you for your feedback.

EDIT 4:

Ok, I managed to do write but once again, I am not sure how to make the input of characters. This is the code:

There are 3 states but it will be true only when going from state A to state C.

    (define (chartest ch)
    (lambda (x) (char=? x ch)))

    (define fsm-trans
       '((A, "a", B), (A, "b", A), (B, "c", C)))

    (define (find-next-state state ch trl)
      (cond
        [(empty? trl) false] 
        [(and (symbol=? state (first (first trl)))
              ((second (first trl)) ch)) <- And also this line returns an error
         (third (first trl))]
        [else (find-next-state state ch (rest trl))]))


    (define fsm-final '(C))

    (define start-state 'A)

    (define (run-fsm start trl final input)
      (cond
        [(empty? input)
         (cond
           [(member start final) true]
           [else false])]
        [else 
         (local ((define next (find-next-state start (first input) trl)))
           (cond
             [(boolean? next) false]
             [else (run-fsm next trl final (rest input))]))]))


    (run-fsm start-state fsm-trans fsm-final (list '("a", "c")))  <- I know this is the last problem with the code, the definition of the input. How can I tell Scheme what characters I want to test?

Thank you for your answer!!!

I am curious: I take it you did not write this fsm? Is this for a homework assignment or are you trying to teach yourself? The code for the FSM looks fine (quite fine, in fact). However, your launch line:

(fsmtrlst (list 'start (lambda (abc112) (char=? abc112 ))))

Makes no sense. Here is why: fsmtrlst is the finite state machine transition list. It was defined in the first big block of code. It is not a function to be called. I believe the function you want to call is run-fsm. That takes a start symbol, a transition list, a list of final states, and an input. The input is not actually a string, but a list. As a consequence, you can launch it with the following line:

(run-fsm 'start fsmtrlst fsmfinal (string->list "abc112"))

That will call run-fsm with the defined transition list fsmtrlst, the defined list of final states, and the input-ready form of the string "abc112".

Incidentally, everything except 'start is defined to be a final (accepting) state. Not all inputs are accepting inputs, though. For example, replacing "abc122" with "abc(122" is not accepted.

Is this what you want?

Update:

Your edit has clarified things. Your definition of fsmstart is fine. You did miss a question mark (?) on one of your char-alphabetic? usages in fsmtrlst. Is your confusion that you don't know how to use your new definitions? First, you should remove the old definitions of fsmtrlst and fsmfinal. Otherwise, you will likely get a duplicate definition error. From your new definition, your line to execute should look like:

(run-fsm fsmstart fsmtrlst fsmfinal (string->list "w00t"))

This will return #t, because "w00t" is a character followed by two numbers, followed by a character.

I speculate that you are still having difficulty with the syntax rules of scheme, and not just problems with the logic of your particular program. You might want to try a simpler exercise.

UPDATE 2: Shouldn't you consider formulating a new question?

Your most recent update has broken the code. The transition portion of the fsm worked because transitions were defined as a list:

(from-state test-function to-state)

You have attempted to create a transition:

(from-state string-literal to-state)

You could change (A, "a", B) to (A (lambda (x) (string=? x "a") B).

When you tried to invoke your function, you took a function that expected a list of characters and gave it a list of list of strings. These are not the same thing. Also, did you notice that you put commas in your lists, but they existed nowhere else in the code? These mistakes are why I suggest you begin a scheme tutorial. These are basic scheme problems, unrelated to your particular exercise. I suggest you rewind your edits to what you had yesterday.

Unfortunately, I can no longer update this answer. I wanted to update my answer so that if someone came along your question with similar concerns, they would see a complete answer. However, you have provided a moving target. Please consider halting your edits and submit a new question when you have one.