I need to build a finite machine constructor that accepts all of the prefixes of a given machine's language. Let's say machine M1's language L(M1)= "abba" then the constructor should produce a new machine M2 such that L(M2)={empty, a, ab, abb, abba}
Now there's a constructor in a library called fsm and it's prototype is like this:
(make-fsa list-of-states alphabet starting-state list-of-final-states list-of-rules)
;List-of-rules is the list of transitions such as (q0 a q1)
;the function returns a finite state machine
I am trying to get every state a final state. But does it work?
The code below is what I've got so far:
#lang racket
(require fsm) ;provides the constructor and getters
(define M1
(make-dfa ;constructor, provided by the fsm library
'(q0 q1 q2) ;states
'(a b) ;alphabet
'q0 ; starting state
'(q2) ;list of final states
'((q0 a q1) ;list of rules
(q0 b q0)
(q1 a q0)
(q1 b q2)
(q2 a q2)
(q2 b q2))))
; new constructor
(define M2
(make-dfa
(sm-getstates M1) ;sm-getstates is a getter that gets a certain machine's states
(sm-getalphabet M1) ;sm-getalphabet is a getter that gets a certain machine's alphabet
(sm-getstart M1) ;sm-getstart is a getter that gets a certain machine's starting state
(sm-getstates M1) ; TURNING EVERY STATE IN M1 A FINAL STATE, BUT DOES IT WORK?
(sm-getrules M1))) ;sm-getrules is a getter that gets a certain machine's list of rules
Your plan does not work. Consider this machine:
States: S,L,F Alphabet: a,b Start state: S Final state S
S-a->L (arrow from S to L given a) S-b->F L-a->L
Strings accepted by this machine: {b}
If you make a new machine where L is a final state, then {empty,a,aa,aaa,...} will be accepted but they are not prefixes in the original machine.
In your construction of M2, only states of M1 that have a path to a final state should become final states in M2.