Finite Automata

• Finomaton is an extension of MetaPost.
• http://www.cs.usfca.edu/~parrt/course/652/projects-Spring-2006/nfa.html using dot to draw DFA and NFA. coding in java.

• man dot
• an example

A DFA which recognize “abcabd” as a substring. the diagram

digraph finite_state_machine {
        node [shape = doublecircle]; "abcabd" ;
        node [shape = circle]; "start" "a" "ab" "abc" "abca" "abcab" ;
        rankdir=LR;
        "start" -> "start" [ label = "b, c, d" ];
        "start" -> "a" [ label = "a" ];
        "a" -> "a" [ label = "a" ];
        "a" -> "start" [ label = "c, d" ];
        "a" -> "ab" [ label = "b" ];
        "ab" -> "a" [ label = "a" ];
        "ab" -> "start" [ label = "b, d" ];
        "ab" -> "abc" [ label = "c" ];
        "abc" -> "start" [ label = "b, c, d" ];
        "abc" -> "abca" [ label = "a" ];
        "abca" -> "a" [ label = "a" ];
        "abca" -> "start" [ label = "c, d" ];
        "abca" -> "abcab" [ label = "b" ];
        "abcab" -> "a" [ label = "a" ];
        "abcab" -> "start" [ label = "b" ];
        "abcab" -> "abc" [ label = "c" ];
        "abcab" -> "abcabd" [ label = "d" ];
        "abcabd" -> "abcabd" [ label = "a, b, c, d" ];
}

A DFA which recognize numbers which conjugate to 3 in binary forms. the diagram

digraph finite_state_machine {
 
        node [shape = doublecircle]; "zero" "0mod3" ;
        node [shape = circle]; "start" "1mod3" "2mod3" ;
        rankdir=LR;
        "start" -> "zero" [ label = "0" ];
        "start" -> "1mod3" [ label = "1" ];
        "1mod3" -> "0mod3" [ label = "1" ];
        "1mod3" -> "2mod3" [ label = "0" ];
        "0mod3" -> "0mod3" [ label = "0" ];
        "0mod3" -> "1mod3" [ label = "1" ];
        "2mod3" -> "1mod3" [ label = "0" ];
        "2mod3" -> "2mod3" [ label = "1" ];
 
}