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 Ints 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])