Da könnte man durch ein bisschen Nachdenken drauf kommen. Wobei ich ja schon zugegeben habe, das mir die Erklärung erst nachträglich beim betrachten des Graphen wie Schuppen von den Augen gefallen ist.
Der Graph ist durch die Überlegung entstanden, dass ein Zustand durch die Eingabe zu maximal zwei Folgezuständen führen kann, und das bei 7 Eingaben maximal ein Baum mit 127 Knoten entsteht. Man kann davon aber Knoten zusammenfassen, da ein Zustand beschrieben werden kann aus der Bitnummer 0 bis 8 (0 = noch kein Bit eingegeben = Startzustand), der Ausgabe die gemacht werden muss (0 oder 1), und dem Prüfbitwert bis dahin (0 oder 1). Das ganze habe ich Kotlin programmiert. Das Programm spuckt den Quelltext im Graphviz-Format aus, mit dem die Grafik erstellt wurde:
Code: Alles auswählen
package de.python_forum.blackjack
data class State (
val bitNumber: Int = 0,
val output: String = "",
val parity: Boolean = false
) : Comparable<State> {
fun nextLevel(bit: Boolean) = this.copy(
bitNumber = bitNumber + 1,
output = if (bit) "1" else "0",
parity = parity xor bit
)
fun parityOutputState() = this.copy(
bitNumber = bitNumber + 1,
output = if (parity) "1" else "0"
)
override fun compareTo(other: State) = when {
bitNumber != other.bitNumber -> bitNumber - other.bitNumber
output != other.output -> output.compareTo(other.output)
else -> parity.compareTo(other.parity)
}
}
class Node(val state: State) : Comparable<Node> {
private val _id = nextId++
private val _children = HashMap<String, Node>()
val id: String
get() = "n$_id"
val children: Iterable<Map.Entry<String, Node>>
get() = _children.asIterable()
fun add(input: String, node: Node) {
_children[input] = node
}
override fun compareTo(other: Node): Int = state.compareTo(other.state)
companion object {
private var nextId: Int = 0
}
}
class Graph(start: State) {
private val stateToNode = HashMap<State, Node>()
val nodes: Iterable<Node>
get() = stateToNode.values
init {
stateToNode[start] = Node(start)
}
fun get(state: State) = stateToNode.computeIfAbsent(state, ::Node)
fun connect(stateA: State, stateB: State, input: String) {
get(stateA).add(input, get(stateB))
}
}
fun buildNodes(bitCount: Int): Iterable<Node> {
val startState = State()
val graph = Graph(startState)
var level = listOf(startState)
repeat(bitCount) {
val nextLevel = ArrayList<State>(level.size * 2)
for (state in level) {
for (bit in arrayOf(false, true)) {
val nextState = state.nextLevel(bit)
nextLevel.add(nextState)
graph.connect(state, nextState, if (bit) "1" else "0")
}
}
level = nextLevel
}
for (state in level.toSet()) {
graph.connect(state, state.parityOutputState(), "")
}
return graph.nodes
}
private fun printNode(node: Node) {
println(" ${node.id} [label=\"${node.state.output}\"];")
}
private fun printEdges(node: Node) {
for ((edge, child) in node.children) {
println(" ${node.id} -> ${child.id}" +
" [label=\"${if (edge.isEmpty()) "ε" else edge}\"]")
}
}
fun printGraphviz(nodes: Iterable<Node>) {
val sortedNodes = nodes.sorted()
println("digraph {")
sortedNodes.forEach(::printNode)
sortedNodes.forEach(::printEdges)
println("}")
}
fun main() {
printGraphviz(buildNodes(7))
}