Deterministic Finite Automata in Swift

DFA.swift

// https://www.youtube.com/watch?v=oHVHkkah3MY&t=979s

struct DFA<State: Hashable, Symbol: Hashable> {
    init(delta: [DFA<State, Symbol>.Pair : State], initialState: State, finalStates: Set<State>) {
        self.delta = delta
        self.initialState = initialState
        self.finalStates = finalStates
    }
    
    struct Pair: Hashable {
        init(_ state: State, _ symbol: Symbol) {
            self.state = state
            self.symbol = symbol
        }
        
        let state: State
        let symbol: Symbol
    }
    
    private let delta: [Pair: State]
    private let initialState: State
    private let finalStates: Set<State>
    
    func run(_ input: Symbol ...) -> Bool {
        finalStates.contains(
            input.reduce(initialState) {
                delta[Pair($0, $1)]!
            }
        )
    }
}

extension DFA where Symbol == Character {
    func run(_ input: String) -> Bool {
        finalStates.contains(
            input.reduce(initialState) {
                delta[Pair($0, $1)]!
            }
        )
    }
}


enum State {
    case x,y,z
}

enum Symbol {
    case a,b
}

// Symbol.a can't follow Symbol.b
let d0 = DFA<State, Symbol>(
    delta: [
        DFA.Pair(.x, .a): .x,
        DFA.Pair(.x, .b): .y,
        DFA.Pair(.y, .a): .z,
        DFA.Pair(.y, .b): .y,
        DFA.Pair(.z, .a): .z,
        DFA.Pair(.z, .b): .z
    ],
    initialState: .x,
    finalStates: [.x, .y]
)

print(d0.run(.a)) // true
print(d0.run(.a, .a)) // true
print(d0.run(.a, .a, .b, .b, .b)) // true

print(d0.run(.b, .a)) // false
print(d0.run(.a, .b, .a)) // false


// "a" can't follow "b"
let d1 = DFA<State, Character>(
    delta: [
        DFA.Pair(.x, "a"): .x,
        DFA.Pair(.x, "b"): .y,
        DFA.Pair(.y, "a"): .z,
        DFA.Pair(.y, "b"): .y,
        DFA.Pair(.z, "a"): .z,
        DFA.Pair(.z, "b"): .z
    ],
    initialState: .x,
    finalStates: [.x, .y]
)

print(d1.run("a")) // true
print(d1.run("aa")) // true
print(d1.run("aabbb")) // true

print(d1.run("ba")) // false
print(d1.run("aba")) // false