A DSL for the Automata Theory Classroom
If you wish to contribute to fsm please read the contribution docs
- Programming-Based Formal Languages and Automata Theory
- Functional Automata - Formal Languages for Computer Science Students
- FSM Error Messages
- Visual Designing and Debugging of Deterministic Finite-State Machines in FSM
- Regular Expressions in a CS Formal Languages Course
- Visualizing a Nondeterministic to Deterministic Finite-State Machine Transformation
- Visualizing Why Nondeterministic Finite-State Automata Reject
- Composing Turing Machines in FSM
Once fsm is installed you use one of the following two options
#lang fsmBelow are some basic examples of how to use fsm. For a more in-depth guide please visit the fsm documentation.
#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))))#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))))#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)))))#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 statesTo visualize a dfa or ndfa create a new file and require fsm. Then provide one of the follwing options:
- sm-visualize <machine-type> To visualize a machine from scratch.
(sm-visualize 'pda) ;; Where the machine type is a symbol- sm-visualize <pre-built-machine> To visualize a pre-built fsm machine.
(sm-visualize a*) ;; See "Building a DFA" for the implementation of a*- 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))- Marco T. Morazán
- Rosario Antunez
- Josephine A. Des Rosiers
- Joshua Schappel
- Sachin Mahashabde
- Tijana Minic
- Oliwia Kempinski
Copyright (c) 2020 by Marco T. Morazan
