Converts a nondeterministic finite automaton with epsilon moves to a minimal deterministic finite automaton and to the corresponding linear grammar.

NfaToDfa.kt

import java.util.*

fun main(args: Array<String>) {
    val a = "a"; val b = "b"; val c = "c"; val d = "d"; val e = "e"; val f = "f"; val g = "g"; val h = "h"; val i = "i"; val j = "j" // for convenience


    // format is delta(first, third) = second. no requirement that third be of the same list as the first and second.
    // nfa without epsilon moves:
    /*val moves = listOf(
            a, b, b,
            a, d, a,
            b, a, b,
            b, c, a,
            c, j, b,
            c, e, b,
            c, e, a,
            d, c, a,
            e, e, a,
            e, e, b,
            f, j, b,
            f, e, a,
            f, g, b,
            g, f, b,
            g, j, a,
            g, g, a,
            g, e, b,
            g, h, a,
            g, h, b,
            h, g, a,
            h, i, b,
            i, f, a,
            i, e, a)*/

    // Input:
    val states = listOf(a, b, c, d, e, f, g, h, i, j) // states list, Q
    val sigma = listOf(a, b) // alphabet, Σ
    // nfa with epsilon moves:
    val moves = listOf( // moves, δ
            a, b, b,
            a, d, a,
            b, a, b,
            b, c, a,
            d, c, a,
            c, c, "",
            c, j, b,
            c, e, a,
            c, e, b,
            e, e, a,
            e, e, b,
            f, j, b,
            f, g, b,
            f, e, a,
            f, e, "",
            g, g, a,
            g, j, a,
            g, f, b,
            g, h, a,
            g, h, b,
            h, g, a,
            h, j, b,
            i, f, a
    )
    val initial = a // initial, q0
    val accepting = listOf(j, g, i) // accepting, F


    if(moves.size % 3 != 0) println("Error! Not div by 3.") else println("${moves.size} moves.")

    val movesTrips = mutableSetOf<Triple<String, String, String>>()
    for(k in (0 until moves.size).step(3)) { // first, convert to triples
        val first = moves[k]
        val second = moves[k+1]
        val third = moves[k+2]
        movesTrips.add(Triple(first, second, third))
    }
    if(movesTrips.map { it.third }.any { it !in sigma && it != "" }) println("Error! Move not in \\Sigma=$sigma.")

    if(movesTrips.map { it.third }.any { it == "" }) { // now, remove epsilon moves
        val copy = listOf(*movesTrips.toTypedArray())
        for(move in copy)
            if(move.third == "") {
                for (move2 in copy)
                    if (move2.second == move.first && move2.third != "")
                        movesTrips.add(Triple(move2.first, move.second, move2.third))
            }
        movesTrips.removeIf { it.third == "" }

    }

    val newStates = mutableListOf<Set<String>>()
    val newAccepting = mutableListOf<Set<String>>()
    for(k in 0 until Math.pow(2.0, states.size.toDouble()).toInt()) { // then, generate power set
        var k2 = k
        var location = 0
        val newState = mutableSetOf<String>()
        while(k2 != 0) {
            if(k2 and 1 == 1) {
                newState.add(states[location])
                if(states[location] in accepting) newAccepting.add(newState)
            }
            k2 = k2 shr 1
            location++
        }
        newStates.add(newState)
    }

    val newMoves = mutableListOf<Triple<Set<String>, Set<String>, String>>()
    for(state in newStates) { // then, generate all possible moves
        for(letter in sigma) {
            val movedTo = mutableSetOf<String>()
            for(inState in state)
                for(otherStates in states)
                    if(Triple(inState, otherStates, letter) in movesTrips) movedTo.add(otherStates)
            if(movedTo.isNotEmpty()) newMoves.add(Triple(state, movedTo.toSortedSet(), letter))
        }
    }

    val finalStates = mutableSetOf<Set<String>>() // then, check where you can get from the initial state
    val stack = Stack<Set<String>>()
    stack.push(setOf(initial))
    while(stack.isNotEmpty()) {
        val s = stack.pop()
        finalStates.add(s)
        for(state in newStates)
            if(state !in finalStates && newMoves.any { it.first == s && it.second == state }) stack.push(state)
    }
    val finalMoves = newMoves.filter { it.first in finalStates }.toMutableSet()
    val finalAccepting = newAccepting.filter { it in finalStates }
    val finalInitial = setOf(initial)

    var flag = false
    for(letter in sigma) for(state in finalStates) // check for stuck automaton
        if(finalMoves.none { it.first == state && it.third == letter }) flag = true
    if(flag) {
        val stuckState = setOf(states.max() + "'")
        finalStates.add(stuckState)
        for(letter in sigma) {
            finalMoves.add(Triple(stuckState, stuckState, letter))
            for(state in finalStates) if(finalMoves.none { it.first == state && it.third == letter })
                finalMoves.add(Triple(state, stuckState, letter))
        }
    }


    val ek = mutableListOf({ s1: Set<String>, s2: Set<String> ->
        (s1 in finalAccepting && s2 in finalAccepting) || (s1 !in finalAccepting && s2 !in finalAccepting)
    }) // q_i ek[idx] q_2 iff there is a word of at most idx[idx] length that seperates them
    val minifiedStates: MutableList<MutableList<MutableSet<Set<String>>>> = mutableListOf()
    for(idx in 0..(finalStates.size - 2)) { // minify automaton states
        minifiedStates.add(mutableListOf())
        for(state1 in finalStates)
            for(state2 in finalStates)
                if(ek[idx](state1, state2)) {
                    var flag2 = false
                    internal@for(state3 in minifiedStates[idx])
                        if(state2 in state3) {
                            state3.add(state1)
                            flag2 = true
                            break@internal
                        } else if(state1 in state3) {
                            state3.add(state2)
                            flag2 = true
                            break@internal
                        }
                    if(!flag2) minifiedStates[idx].add(mutableSetOf(state1, state2))
                }

        ek.add {
            s1, s2 ->
            if(!ek.any { ek.indexOf(it) <= idx && it(s1, s2) }) false
            else {
                val nextMoves = mutableListOf<Pair<Set<String>, Set<String>>>()
                for(letter in sigma)
                    nextMoves.add(finalMoves.first { it.first == s1 && it.third == letter }.second to finalMoves.first { it.first == s2 && it.third == letter }.second)
                nextMoves.all { ek[idx](it.first, it.second) }
            }

        }
    }
    val minifiedInitial = minifiedStates.last().first { finalInitial in it }

    val minifiedMoves = mutableSetOf<Triple<Set<Set<String>>, Set<Set<String>>, String>>()
    for(move in finalMoves) // fix automaton moves according to minification
        minifiedMoves.add(Triple(minifiedStates.last().first { move.first in it }, minifiedStates.last().first { move.second in it }, move.third))

    var letter = "a"
    val renamedStates = mutableMapOf<Set<Set<String>>, String>()
    for(state in minifiedStates.last()) { // rename states to make it easier to read
        renamedStates[state] = letter
        val pref = letter.substring(0 until (letter.length - 1))
        var lastChar = letter.last()
        if(lastChar != 'Z') {
            lastChar += 1
            letter = pref + lastChar
        } else {
            letter += "a"
        }

    }
    val renamedInitial = renamedStates[minifiedInitial]!!

    val renamedMoves = mutableSetOf<Triple<String, String, String>>() // rename moves
    for(move in minifiedMoves)
        renamedMoves.add(Triple(renamedStates[move.first]!!, renamedStates[move.second]!!, move.third))

    val renamedAccepting = renamedStates.filter { it.key.any { it in finalAccepting } } // check for accepting states

    println("States in new automaton: Q={" + renamedStates.values.joinToString() + "} (${renamedStates.values.size} states)")
    println("Moves in new automaton: δ={" + renamedMoves.joinToString { "${it.first} --${it.third}> ${it.second}" } + "} (${renamedMoves.size} moves)")
    println("Accepting states in new automaton: F={" + renamedAccepting.values.joinToString() + "} (${renamedAccepting.values.size} states)")
    println("Initial state: q0=$renamedInitial")
    println("A=($sigma, Q, q0, F, δ)")

    println("\nList of congurency classes of initial automaton states:")
    for((idx, clazz) in minifiedStates.withIndex())
        println("PI_$idx = {${clazz.joinToString()}}")

    // conversion to regular grammar
    val grammarRules = mutableListOf<Pair<String, MutableList<Pair<String, String?>>>>()
    val variables = renamedStates.values.indices.map { if(it == 0) "S" else "V_$it" }
    val grammarInitial = variables[renamedStates.values.indexOf(renamedInitial)]
    for(move in renamedMoves) {
        val set = renamedStates.values
        grammarRules.add(Pair(variables[set.indexOf(move.first)], mutableListOf(move.third to variables[set.indexOf(move.second)] as String?)))
        if(move.second in renamedAccepting.values) grammarRules.add(Pair(variables[set.indexOf(move.second)], mutableListOf(move.third to null as String?)))
    }
    val minifiedGrammarRules = mutableListOf<Pair<String, MutableList<Pair<String, String?>>>>()
    for(rule in grammarRules) {
        val attempt = minifiedGrammarRules.firstOrNull { it.first == rule.first }
        if(attempt != null) {
            attempt.second += rule.second.first()
        } else minifiedGrammarRules.add(Pair(rule.first, rule.second))
    }
    val minifiedGrammarRulesString = minifiedGrammarRules.joinToString { it.first + " -> " + it.second.joinToString("|") { if(it.second == null) it.first else it.first + it.second } }
    println("\nCorresponding regular grammar:")
    println("Variables: V={${variables.joinToString()}}")
    println("Starting variable: S=$grammarInitial")
    println("Rules: P={$minifiedGrammarRulesString}")
    println("G=(V, $sigma, S, P)")
}