Finite state machine constructor - Racket Language

Question

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

soegaard soegaard · Accepted Answer · 2015-03-11T18:04:21

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.

Finite state machine constructor - Racket Language

1 Answers