I’ve been reading Understanding Computation by Tom Suart, and it reminds me of my first CS class in grad school where I learned about and struggled to implement finite automata. I think one major lesson from that experience was to forget about the pictures of circles and loops on the blackboard, and figure out the bare minimum needed to represent the idea. In the case of finite automata, the bare minimum was that there was a state, and a set of rules that modified the state; each rule was composed of a current state, an input, and a next state. I decided to implement a simple finite automata in Swift using a list of `Int`

s as states, and a single `Int`

as input.

import Cocoa // current state, input -> next state struct State: Equatable { var state: [Int] init(withData state: [Int]) { self.state = state } static func ==(lhs: State, rhs: State) -> Bool { if lhs.state == rhs.state { return true } return false } } struct Rule { var currentState: State var input: Int var nextState: State init(currentState: State, input: Int, nextState: State) { self.currentState = currentState self.input = input self.nextState = nextState } init(currentState: [Int], input: Int, nextState: [Int]) { self.currentState = State(withData: currentState) self.input = input self.nextState = State(withData: nextState) } } struct DFA { var state: State var acceptState: State var accepting: Bool { return state == acceptState } var rules: [Rule] mutating func applyRule(withInput input: Int) { for rule in rules { if rule.currentState == state && rule.input == input { state = rule.nextState break } } } mutating func applyRules(withInput input: Int) { var previousState: State repeat { previousState = state applyRule(withInput: input) } while previousState != state } mutating func read(input: [Int]) { print(dfa.state) print(dfa.accepting) print("\n") for item in input { applyRules(withInput: item) print(state) print(accepting) print("\n") } } } var rules:[Rule] = [ Rule(currentState: [0,1], input:0, nextState: [0,0]), Rule(currentState: [0,0], input:0, nextState: [1,0]) ] var initialState: State = State(withData: [0,1]) var acceptState: State = State(withData: [1,0]) var dfa = DFA(state: initialState, acceptState:acceptState, rules: rules) dfa.read(input: [1,0])