typealias State = String
typealias Table = HashSet<Triple<State, State, Char?>>

// Kotlin feature: extension function
fun Table.add(source: State, target: State, label: Char?): Table {
    this.add(Triple(source, target, label))
    return this
}

class Automaton (
    val S: Set<State>,
    val s0: State,
    val F: Set<State>,
    val Δ: Table,
)

val states = setOf("1", "2", "3")
val finals = setOf("1")
val initial = "1"
val transitions = Table()
    .add("1", "2", 'b')
    .add("1", "3", null)
    .add("2", "2", 'a')
    .add("2", "3", 'a')
    .add("2", "3", 'b')
    .add("3", "1", 'a')
    
val automaton = Automaton(states, initial, finals, transitions)

// Closure is an extension function of Automaton.
fun Automaton.closure(T: Iterable<State>): Set<State> {
    val result = mutableSetOf<State>().apply {
        addAll(T)
    }

    do {
        val newResultStates = this.Δ.filter {
            triple ->
            val (source, target, label) = triple
            ((source in result) && 
                    (label == null) && 
                    !(target in result))
        }.map {
            triple -> triple.second
        }
        
        result.addAll(newResultStates)
    } while(newResultStates.isNotEmpty())
    
    return result
}

// Do a simple test
automaton.closure(listOf("1"))

fun Automaton.reachable(T: Iterable<State>, x: String): Set<State> {
    var result:Set<State> = this.closure(T)
    for(c:Char in x) {
        result = this.Δ.filter {
            (it.first in result) && it.third == c
        }.map {
            it.second
        }.toSet()
        
        result = this.closure(result)
    }
    
    return result
}

println("ba: " + automaton.reachable(setOf(automaton.s0), "ba"))
println("bb: " + automaton.reachable(setOf(automaton.s0), "bb"))
println("bbc: " + automaton.reachable(setOf(automaton.s0), "bbc"))

fun Automaton.matches(x: String): Boolean =
    this.reachable(listOf(s0), x).intersect(F).isNotEmpty()

val strings = listOf(
    "aabb",
    "ab",
    "aaaaaaa",
    "bba",
    "bbb",
)

for(x in strings) {
    println("${x}: ${automaton.matches(x)}")
}