FSM

A DSL for the Automata Theory Classroom

Documentation

Installation

Contributing

If you wish to contribute to fsm please read the contribution docs

Publications

Getting Started

Once fsm is installed you use one of the following two options

#lang fsm

Basic Usage

Below are some basic examples of how to use fsm. For a more in-depth guide please visit the fsm documentation.

Building a DFA

#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 a NDFA

#lang fsm

; L(KLEENESTAR-abUaba) = (abUaba)*
(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 a PDA

#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 a TM

#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

Visualizing a Machine

To visualize a dfa or ndfa create a new file and require fsm. Then provide one of the follwing options:

1) sm-visualize <machine-type> To visualize a machine from scratch.

(sm-visualize 'pda) ;; Where the machine type is a symbol

2) sm-visualize <pre-built-machine> To visualize a pre-built fsm machine.

(sm-visualize a*) ;; See "Building a DFA" for the implementation of a*

3) sm-visualize <pre-built-machine (state invariant-function)> To visualize a pre-built fsm machine with associated state invariants. Note that (state invariant-function)* is a arbitrary number of tuples.

;; Invariant functions
(define INV1 (lambda (v) true))
(define INV2 (lambda (v) false))

;; Visualize the machine 
(sm-visualize a* (list 'S INV1) (list 'F INV2))

morazanm / fsm

readme

FSM