FSM

Constructing Machines

Here you can find examples of how to construct state machines in FSM.

Building DFAs

#lang fsm
; L(a*a) = {w | w starts and ends with an a}
(define a*a (make-dfa '(S F A)         ;the states
                      '(a b)           ;the alphabet
                      'S               ;the starting state
                      '(F)             ;final states
                      '((S a F)        ;the transition function
                        (F a F)
                        (F b A)
                        (A a F)
                        (A b A))))

Building NDFAs

#lang fsm

; L(KLEENESTAR-ab U aba) = (ab U aba)*
(define KLEENESTAR-abUaba (make-ndfa '(Q-0 Q-1 Q-2 Q-3 Q-4 Q-5) ;the states
                                     '(a b)                     ;the alphabet
                                     'Q-0                       ;the starting state
                                     '(Q-0)                     ;the final states
                                     `((Q-0 a Q-1)              ;the transition relation
                                       (Q-1 b Q-2)
                                       (Q-2 a Q-3)
                                       (Q-3 ,EMP Q-0)
                                       (Q-0 a Q-4)
                                       (Q-4 b Q-5)
                                       (Q-5 ,EMP Q-0))))

Building PDAs

#lang fsm

    ; L = {wcw^r | w in {a, b)*}
    (define pda-wcw^r (make-ndpda '(S M N F)                  ;the states
                                  '(a b c)                    ;the alphabet
                                  '(a b)                      ;the stack alphabet
                                  'S                          ;the starting state
                                  '(F)                        ;the final state
                                  `(((S ,EMP ,EMP) (M ,EMP))  ;the transition relation
                                    ((M a ,EMP) (M (a)))
                                    ((M b ,EMP) (M (b)))
                                    ((M c ,EMP) (N ,EMP))
                                    ((N a (a)) (N ,EMP))
                                    ((N b (b)) (N ,EMP))
                                    ((N ,EMP ,EMP) (F ,EMP)))))

Building TMs

Turing Machines

#lang fsm

; write "a" on tape
(define Ma (make-tm '(S H)                  ;the states
                    `(a b ,LM)              ;the alphabet
                    `(((S ,LM) (S ,RIGHT))  ;the transition relation
                      ((S a) (H a))
                      ((S b) (H a))
                      ((S ,BLANK) (H a)))
                    'S                      ;the starting state
                    '(H)))                  ;the halting states

Language Recognizers

#lang fsm

; All a's on tape
(define Alla (make-tm '(S Y N)        
                      `(a b ,LM)
                      `(((S a) (S ,RIGHT))
                        ((S b) (N b))
                        ((S ,BLANK) (Y ,BLANK)))
                      'S
                      '(Y N)
                      'Y))          ;the accepting state

Visualizing Machines

Here you can find examples of how to visualize state machines in FSM.

#lang fsm
;; All machines can be visualized using the following three formats
;; 1)
;;    Use the visualization tool to build a machine from scratch
(sm-visualize 'machine-type)   

;; 2)
;;    Use the visualization tool to view a pre-built machine
(sm-visualize machine)       

;; 3)
;;    Use the visualization tool to view a pre-built machine, where states
;;     are associated with predicates
(sm-visualize machine [(list 'state procedure)*])

Lets visualize a machine:

#lang fsm
#| From Scratch |#
(sm-visualize 'dfa)


#| Prebuilt |#
;; see a*a above
(sm-visualize a*a)

Execution of a*a on the input: a b a b a

#lang fsm
#| With Invariants |#
(define S-INV empty?)

(define (F-INV consumed-input)
  (and (eq? (first consumed-input) 'a)
       (eq? (last consumed-input) 'a)))

(define (A-INV consumed-input)
  (and (eq? (first consumed-input) 'a)
       (not (eq? (last consumed-input) 'a))))

(define (DEAD-INV consumed-input)
  (not (eq? (first consumed-input) 'a)))


;; visualize the machine
(sm-visualize a*a (list 'S S-INV) 
                  (list 'F F-INV)
                  (list 'A A-INV) 
                  (list 'ds DEAD-INV))

Execution of a*a on the input: a b a b a, with invariants visualized

Accessors and Mutators

Here you can find examples of how to use FSM (See documentation for detailed explanation).

#lang fsm
(sm-start a*a)   ;; Gets starting states
(sm-finals a*a)  ;; Gets final states
(sm-rules a*a)   ;; Gets rules 
(sm-alpha a*a)   ;; Gets alphabet
(sm-type a*a)    ;; Returns a symbol indicating the type of the given machine
(sm-gamma a*a)   ;; Returns the stack alphabet of the given pushdown automaton
(sm-apply a*a '(a b a b a))           ;;  Applies a input to a given machine 
(sm-showtransitions a*a '(a a b b a)) ;;  Shows the transitions for a input to a given machine 
(sm-test a*a 420)   ;; Tests the machine on n randomly generated inputs

Examples