Related sites: | site map |

# aiju.de Home of aiju

- › about me/
- › b/
- » code/
- - › RatJS
  - › homework/
  - » k/
  - - › cluster
    - › coins
    - › eratothenes
    - › euler phi
    - › feigenbaum
    - › fibonacci
    - » fsm
    - › molecule
    - › pascal
    - › qsort
    - › sierpinski
    - › tictactoe
  - › misc/
  - › pdp11/
- › donate
- › electronics/
- › legal
- › misc/
- › plan 9/

# FSM minimization

This program minimizes finite state machines using the implication table method.

    out:0
    states:((1 2; 0 0);(3 4; 0 0);(5 6; 0 0);(0 0; 0 0);(0 0; 1 0);(0 0; 0 0);(0 0; 1 0))
    sp:({x,/:\:x}@,:'states)
    start:~/''sp@\:\:\:1
    sel:{(2*~0=x)#''+:''sp@\:\:\:0}
    step:{{&/(#x),x}'' #:''' (x@/)'''x} sel@
    res:&:'~0=step/start
    pp:{[x;z] (,"digraph {"), (,/{[x]:[(=/z@/:states[*x;0])&=/states[*x;1];,"S",($*x)," -> S",($z[states[*x;0;0]])," [label=\"/",($states[*x;1;0]),"\"];";{[y]"S",($*x)," -> S",($z[states[*x;0;y]])," [label=\"",($y),"/",($states[*x;1;y]),"\"];"}'0 1]}'x), (,,"}")}
    :[out;`0:pp[?res;*:'res];`0:pp[,:' (!#states);!#states]]

The `out` parameter at the top defines whether the optimized (1) or unoptimized (0) version should be outputted. Yes, that `pp` line is ugly.