Skip to content

Instantly share code, notes, and snippets.

@Eladkay
Last active May 15, 2020 12:36
Show Gist options
  • Save Eladkay/efc17d3af2363b54f85d2d732ddedb94 to your computer and use it in GitHub Desktop.
Save Eladkay/efc17d3af2363b54f85d2d732ddedb94 to your computer and use it in GitHub Desktop.
Converts a nondeterministic finite automaton with epsilon moves to a minimal deterministic finite automaton and to the corresponding linear grammar.
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)")
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment