Skip to content

Instantly share code, notes, and snippets.

@erkekin

erkekin/DFA.swift

Last active March 16, 2023 23:26
Show Gist options
  • Save erkekin/43311e154da01271f0ed9936217a0af3 to your computer and use it in GitHub Desktop.
Save erkekin/43311e154da01271f0ed9936217a0af3 to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. erkekin revised this gist Mar 16, 2023. 1 changed file with 16 additions and 16 deletions.
    32 changes: 16 additions & 16 deletions DFA.swift
    View file
    Original file line number Diff line number Diff line change
    @@ -23,8 +23,8 @@ struct DFA<State: Hashable, Symbol: Hashable> {

    func run(_ input: Symbol ...) -> Bool {
    finalStates.contains(
    input.reduce(into: initialState) {
    $0 = delta[Pair($0, $1)]!
    input.reduce(initialState) {
    delta[Pair($0, $1)]!
    }
    )
    }
    @@ -33,8 +33,8 @@ struct DFA<State: Hashable, Symbol: Hashable> {
    extension DFA where Symbol == Character {
    func run(_ input: String) -> Bool {
    finalStates.contains(
    input.reduce(into: initialState) {
    $0 = delta[Pair($0, $1)]!
    input.reduce(initialState) {
    delta[Pair($0, $1)]!
    }
    )
    }
    @@ -49,7 +49,7 @@ enum Symbol {
    case a,b
    }

    // "a" can't come after "b"
    // Symbol.a can't follow Symbol.b
    let d0 = DFA<State, Symbol>(
    delta: [
    DFA.Pair(.x, .a): .x,
    @@ -63,15 +63,15 @@ let d0 = DFA<State, Symbol>(
    finalStates: [.x, .y]
    )

    print(d0.run(.a))
    print(d0.run(.a, .a))
    print(d0.run(.a, .a, .b, .b, .b))
    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))
    print(d0.run(.a, .b, .a))
    print(d0.run(.b, .a)) // false
    print(d0.run(.a, .b, .a)) // false


    // "a" can't come after "b"
    // "a" can't follow "b"
    let d1 = DFA<State, Character>(
    delta: [
    DFA.Pair(.x, "a"): .x,
    @@ -85,9 +85,9 @@ let d1 = DFA<State, Character>(
    finalStates: [.x, .y]
    )

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

    print(d1.run("ba"))
    print(d1.run("aba"))
    print(d1.run("ba")) // false
    print(d1.run("aba")) // false
  2. erkekin created this gist Mar 16, 2023.
    93 changes: 93 additions & 0 deletions DFA.swift
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,93 @@
    // 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(into: initialState) {
    $0 = delta[Pair($0, $1)]!
    }
    )
    }
    }

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


    enum State {
    case x,y,z
    }

    enum Symbol {
    case a,b
    }

    // "a" can't come after "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))
    print(d0.run(.a, .a))
    print(d0.run(.a, .a, .b, .b, .b))

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


    // "a" can't come after "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"))
    print(d1.run("aa"))
    print(d1.run("aabbb"))

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