Last active
January 3, 2019 01:05
-
-
Save gdejohn/a815eb4760b3f17af930 to your computer and use it in GitHub Desktop.
Deterministic finite automaton
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
shared void run() { | |
assert (exists string = process.readLine()); | |
print(divisibleByTwoOrThree.accepts(string)); | |
} | |
"Start state of a DFA that recognizes unsigned decimal numbers divisible by | |
two or three. Strings with leading zeros are rejected." | |
object divisibleByTwoOrThree satisfies State<Character> { | |
transition(Character symbol) => switch (symbol) | |
case ('0') zero | |
case ('3' | '6' | '9') divisibleByThree | |
case ('4') oneModThreeEven | |
case ('1' | '7') oneModThreeOdd | |
case ('2' | '8') twoModThreeEven | |
case ('5') twoModThreeOdd | |
else trap; | |
} | |
"The number 0." | |
object zero satisfies State<Character> { | |
accepting = true; | |
} | |
"Divisible by 3 because sum of digits is divisible by 3." | |
object divisibleByThree satisfies State<Character> { | |
accepting = true; | |
transition(Character symbol) => switch (symbol) | |
case ('0' | '3' | '6' | '9') this | |
case ('4') oneModThreeEven | |
case ('1' | '7') oneModThreeOdd | |
case ('2' | '8') twoModThreeEven | |
case ('5') twoModThreeOdd | |
else trap; | |
} | |
"Even number, sum of digits congruent to 1 modulo 3." | |
object oneModThreeEven satisfies State<Character> { | |
accepting = true; | |
transition(Character symbol) => switch (symbol) | |
case ('2' | '5' | '8') divisibleByThree | |
case ('0' | '6') this | |
case ('3' | '9') oneModThreeOdd | |
case ('4') twoModThreeEven | |
case ('1' | '7') twoModThreeOdd | |
else trap; | |
} | |
"Odd number, sum of digits congruent to 1 modulo 3." | |
object oneModThreeOdd satisfies State<Character> { | |
transition(Character symbol) => switch (symbol) | |
case ('2' | '5' | '8') divisibleByThree | |
case ('0' | '6') oneModThreeEven | |
case ('3' | '9') this | |
case ('4') twoModThreeEven | |
case ('1' | '7') twoModThreeOdd | |
else trap; | |
} | |
"Even number, sum of digits congruent to 2 modulo 3." | |
object twoModThreeEven satisfies State<Character> { | |
accepting = true; | |
transition(Character symbol) => switch (symbol) | |
case ('1' | '4' | '7') divisibleByThree | |
case ('2' | '8') oneModThreeEven | |
case ('5') oneModThreeOdd | |
case ('0' | '6') this | |
case ('3' | '9') twoModThreeOdd | |
else trap; | |
} | |
"Odd number, sum of digits congruent to 2 modulo 3." | |
object twoModThreeOdd satisfies State<Character> { | |
transition(Character symbol) => switch (symbol) | |
case ('1' | '4' | '7') divisibleByThree | |
case ('2' | '8') oneModThreeEven | |
case ('5') oneModThreeOdd | |
case ('0' | '6') twoModThreeEven | |
case ('3' | '9') this | |
else trap; | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
"A state in a deterministic finite automaton." | |
shared interface State<in Symbol> { | |
"Returns [[true]] if this is an accept state, else [[false]]." | |
shared default Boolean accepting => false; | |
"Returns the next state given the next [[symbol]]." | |
shared default State<Symbol> transition(Symbol symbol) => trap; | |
"Returns [[true]] if the given [[string]] is accepted by the implicit DFA | |
starting at this state, else [[false]]. Accepted strings are words in the | |
language recognized by that DFA." | |
shared Boolean accepts({Symbol*} string) | |
=> string.fold(this)(uncurry(State<Symbol>.transition)).accepting; | |
} | |
"Always transitions to itself, accepts nothing." | |
shared object trap satisfies State<Anything> {} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment