A finite deterministic automata that duplicates natural numbers

duplication_automata.js

function duplication_automata() {
	const digits = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
	const vertices = [{type: 'start'}, {type: 'stop'}]
	const edges = []

	for (const digit of digits)
		vertices.push({type: 'internal', digit})

	for (const v of vertices) {
		const add_edge = (to, match, output) =>
			edges.push({
				from: v,
				to,
				match: match.toString(),
				output
			})
		const carry = (v) => v >= 5 ? 1 : 0
		if (v.type === 'start')
			for (const u of vertices)
				if (u.type === 'internal')
					add_edge(u, u.digit, carry(u.digit) || '')
		if (v.type === 'internal') {
			const double = v.digit * 2 % 10
			for (const u of vertices)
				if (u.type === 'internal')
					add_edge(u, u.digit, double + carry(u.digit))
				else if (u.type === 'stop')
					add_edge(u, 'END', double)
		}
	}
	return { start: vertices[0], edges }
}

function run_automata(automata, input) {
	let v = automata.start
	let output = ''
	const advance_with = (i, fragment) => {
		for (const edge of automata.edges)
			if (edge.from === v && edge.match === fragment) {
				output += edge.output
				v = edge.to
				return
			}
		throw new Error(`Failed to match at index ${i} of ${input}. Current state: ${JSON.stringify(v)}`)
	}
	for (let i = 0; i < input.length; i++) {
		const fragment = input[i]
		advance_with(i, fragment)
	}
	advance_with(input.length, 'END')
	if (v.type !== 'stop')
		throw new Error(`Automata ended in a non-accepting state. Current state: ${JSON.stringify(v)}`)

	return output
}

function to_dotfile(automata) {
	const format_vert = (v) => {
		if (v.type === 'start') return '"Start"'
		if (v.type === 'internal') return `"Read ${v.digit}"`
		if (v.type === 'stop') return `"End"`
	}
	let output = 'digraph {\n'
	output += '\trankdir=LR\n'
	for (const edge of automata.edges) {
		output += '\t'
		output += format_vert(edge.from)
		output += ' -> '
		output += format_vert(edge.to)
		output += ` [label="match ${edge.match}, output '${edge.output}'"]`
		output += '\n'
	}
	output += '}\n'
	return output
}

function test_duplication_automata() {
	const assert = (expected, got) => {
		if (expected !== got)
			throw new Error(`Assertion Failed. Expected: ${expected}, Got: ${got}`)
	}
	const automata = duplication_automata()
	const duplicate = (x) => run_automata(automata, x.toString())
	for (let i = 0; i < 9999; i++) {
		assert((2*i).toString(), duplicate(i))
	}
	assert('02', duplicate('01'))
	assert('18', duplicate('09'))
}

test_duplication_automata()
console.log(to_dotfile(duplication_automata()))