js/back.js - master - PavelMask/MyCourseWork

js/back.js
721 строка18 KB
PavelMask
Файлы курсовой работы (версия 1)
07 июн 2026, 21:26
07 июн 2026, 21:26491ad5e
"use strict";
function eClosure(automaton) {
    const epsClosure = [];
    const totalStates = automaton.states;
    
    for (let idx = totalStates - 1; idx >= 0; idx--) {
        epsClosure[idx] = new Set([idx]);
        const initialMembers = Array.from(epsClosure[idx]);
        
        for (let pos = 0; pos < initialMembers.length; pos++) {
            const sourceState = initialMembers[pos];
            const outgoingEdges = automaton.edges[sourceState];
            
            if (outgoingEdges && outgoingEdges["0"]) {
                const epsilonTargets = outgoingEdges["0"];
                epsilonTargets.forEach(function(targetState) {
                    if (targetState > idx) {
                        epsClosure[targetState].forEach(function(descendant) {
                            epsClosure[idx].add(descendant);
                        });
                    } else {
                        epsClosure[idx].add(targetState);
                    }
                });
            }
        }
    }
    
    return epsClosure;
}

function uniteEdges(targetAutomaton, sourceAutomaton) {
    const offset = targetAutomaton.states;
    
    for (let stateIdx = 0; stateIdx < sourceAutomaton.states; stateIdx++) {
        const stateTransitions = sourceAutomaton.edges[stateIdx];
        if (stateTransitions === undefined) continue;
        
        for (const inputSymbol in stateTransitions) {
            const destinations = stateTransitions[inputSymbol];
            destinations.forEach(function(destState) {
                addTransition(
                    targetAutomaton,
                    stateIdx + offset,
                    destState + offset,
                    inputSymbol
                );
            });
        }
    }
}

function eliminateUnreachable(automaton, automatonCopy) {
    const reachableSet = new Set([automaton.start]);
    automatonCopy.unreachable = [];
    
    for (const currentState of reachableSet) {
        const outgoingEdges = automaton.edges[currentState];
        if (outgoingEdges === undefined) continue;
        
        for (const inputSymbol in outgoingEdges) {
            outgoingEdges[inputSymbol].forEach(function(targetState) {
                reachableSet.add(targetState);
            });
        }
    }
    
    for (let stateId = automaton.states - 1; stateId >= 0; stateId--) {
        if (!reachableSet.has(stateId)) {
            removeState(automaton, stateId);
            automatonCopy.unreachable.push(stateId);
        }
    }
    
    return automaton;
}

function constructNFAe(tree) {
	var NFAl = {
		alphabet: new Set([]),
		states: 0,
		start: 0,
		edges: [],
		outgoing: [],
		incoming: [],
		accepting: new Set([])
	}

	switch (tree.type) {
		case "or":
			NFAl.states++;
			var oldaccepting = new Set([]);
			for (var i = 0; i < tree.value.length; i++) {
				var NFAltemp = constructNFAe(tree.value[i]);
				NFAltemp.alphabet.forEach(function (val) {
					NFAl.alphabet.add(val);
				});
				uniteEdges(NFAl, NFAltemp);
				addTransition(NFAl, 0, NFAltemp.start + NFAl.states, "0");
				oldaccepting.add(NFAltemp.accepting.values().next().value + NFAl.states);
				NFAl.states += NFAltemp.states;
			}
			NFAl.states++;
			oldaccepting.forEach(function (val) {
				addTransition(NFAl, val, NFAl.states - 1, "0");
			});
			NFAl.accepting.add(NFAl.states - 1);
			return NFAl;

		case "concat":
			for (var i = 0; i < tree.value.length; i++) {
				var NFAltemp = constructNFAe(tree.value[i]);
				NFAltemp.alphabet.forEach(function (val) {
					NFAl.alphabet.add(val);
				});
				uniteEdges(NFAl, NFAltemp);
				if (i == 0)
					NFAl.start = NFAltemp.start;
				else
					addTransition(NFAl, prev, NFAltemp.start + NFAl.states, "0");
				if (i == tree.value.length - 1)
					NFAl.accepting.add(NFAltemp.accepting.values().next().value + NFAl.states);
				var prev = NFAltemp.accepting.values().next().value + NFAl.states;
				NFAl.states += NFAltemp.states;
			}
			return NFAl

		case "star":
			var NFAltemp = constructNFAe(tree.value);
			addTransition(NFAltemp, NFAltemp.states, NFAltemp.start, "0");
			addTransition(NFAltemp, NFAltemp.accepting.values().next().value, NFAltemp.states, "0");
			NFAltemp.states++;
			NFAltemp.accepting = new Set([NFAltemp.states - 1]);
			NFAltemp.start = NFAltemp.states - 1;
			return NFAltemp;

		case "letter":
			NFAl.alphabet.add(tree.value);
			NFAl.states = 2;
			addTransition(NFAl, 0, 1, tree.value);
			NFAl.accepting.add(1);
			return NFAl;

		case "lambda":
			NFAl.states = 1;
			NFAl.accepting.add(0);
			return NFAl;

		default:
			console.log("Unknown type");
	}

}



function RedundantStates(NFAl) {
	for (var i = NFAl.states - 1; i >= 0; i--) {
		var removed = false;
		if (NFAl.outgoing[i] == 1) {
			for (var symbol in NFAl.edges[i]) {
				if (symbol == "0" && !NFAl.edges[i][symbol].has(i) && NFAl.edges[i][symbol] != undefined && NFAl.edges[i][symbol].size != 0) {
					removeRedundantState(NFAl, i, NFAl.edges[i][symbol].values().next().value, false);
					removed = true;
					break;
				}
			}
		}
		if (NFAl.incoming[i] == 1 && !removed) {
			for (var j = 0; j < NFAl.states; j++) {
				if (removed)
					break;
				if (NFAl.edges[j] == undefined || NFAl.edges[j]["0"] == undefined)
					continue;
				var it = NFAl.edges[j]["0"].values();
				for (var val = it.next().value; val !== undefined; val = it.next().value) {
					if (val == i) {
						removeRedundantState(NFAl, i, j, true);
						removed = true;
						break;
					}
				};
			}
		}
	}
	return NFAl;
}

function removeRedundantState(NFAl, state, tofr, tag) {
	if (NFAl.accepting.has(state) || NFAl.start == state)
		return;
	if (!tag) {
		for (var i = 0; i < NFAl.states; i++) {
			for (var symbol in NFAl.edges[i]) {
				NFAl.edges[i][symbol].forEach(function (value) {
					if (value == state) {
						addTransition(NFAl, i, tofr, symbol);
						removeTransition(NFAl, i, state, symbol);
					}
				});
			}
		}
		removeTransition(NFAl, state, tofr, "0");
	}
	else {
		for (var symbol in NFAl.edges[state]) {
			NFAl.edges[state][symbol].forEach(function (value) {
				addTransition(NFAl, tofr, value, symbol);
				removeTransition(NFAl, state, value, symbol);
			});
		}
		removeTransition(NFAl, tofr, state, "0");
	}

	removeState(NFAl, state);
}


function TransitionsRemove(NFAl) {
	var closure = eClosure(NFAl); 
	NFAl.ledges = new Set();
	NFAl.newedges = new Set();
	NFAl.normaledges = new Set();
	NFAl.newaccepting = [];
	for (var i = 0; i < NFAl.states; i++) {
		if (NFAl.edges[i] == undefined)
			continue;
		for (var symbol in NFAl.edges[i]) {
			if (NFAl.edges[i][symbol] != undefined) {
				NFAl.edges[i][symbol].forEach(function (val) {
					if (symbol != "0")
						NFAl.normaledges.add([i, val, symbol]);
					else {
						NFAl.ledges.add([i, val, "0"]);
					}
				});
			}
		}
	}
	for (var i = 0; i < NFAl.states; i++) {
		closure[i].forEach(function (val) {
			if (NFAl.edges[val] != undefined) {
				for (var symbol in NFAl.edges[val]) {
					if (symbol != "0" && NFAl.edges[val][symbol] != undefined) {
						NFAl.edges[val][symbol].forEach(function (val2) {
							if (NFAl.edges[i] == undefined || NFAl.edges[i][symbol] == undefined || !NFAl.edges[i][symbol].has(val2)) {
								if (addTransition(NFAl, i, val2, symbol))
									NFAl.newedges.add([i, val2, symbol]);
							}
						});
					}
				}
			}
			if (NFAl.accepting.has(val) && !NFAl.accepting.has(i)) {
				NFAl.accepting.add(i);
				NFAl.newaccepting.push(i);
			}
		});
	}
	for (var i = 0; i < NFAl.states; i++) {
		if (NFAl.edges[i] == undefined || NFAl.edges[i]["0"] == undefined)
			continue;
		NFAl.edges[i]["0"].forEach(function (val) {
			removeTransition(NFAl, i, val, "0");
		});
	}
	return NFAl;
}


function subsetConstruction(NFA) { 
	var DFA = {
		alphabet: new Set(NFA.alphabet), 
		states: 1,                       
		start: 0,                				 
		edges: [],                       
		outgoing: [],      							 
		incoming: [],      						 	 
		accepting: new Set(),        		 
		statescor: []										 
	}
	DFA.statescor[0] = [NFA.start]; 
	if (NFA.accepting.has(NFA.start))
		DFA.accepting.add(0);
	var reachable = []; 
	for (var i = 0; i < DFA.states; i++) {
		DFA.alphabet.forEach(function (symbol) {
			reachable = []; 
			for (var j = 0; j < DFA.statescor[i].length; j++) {
				if (NFA.edges[DFA.statescor[i][j]] != undefined && NFA.edges[DFA.statescor[i][j]][symbol] != undefined) {
					NFA.edges[DFA.statescor[i][j]][symbol].forEach(function (val) {
						if (!reachable.includes(val))
							reachable.push(val);
					})
				}
			}
			reachable.sort(function (a, b) {
				return a - b;
			});
			var index = ArrayHasArray(DFA.statescor, reachable);
			if (index != -1) { 
				addTransition(DFA, i, index, symbol);
			}
			else { 
				var isaccepting = false; 
				for (var j = 0; j < reachable.length; j++) {
					if (NFA.accepting.has(reachable[j]))
						isaccepting = true;
				}
				if (isaccepting) {
					DFA.accepting.add(DFA.states);
				}
				addTransition(DFA, i, DFA.states, symbol);
				DFA.statescor[DFA.states] = reachable;
				DFA.states++;
			}
		})
	}
	return DFA;
}


function minimizeDFA(DFA) { 
	var equivalent = []; 
	for (var i = 0; i < DFA.states; i++) {
		equivalent[i] = [];
		for (var j = i; j < DFA.states; j++) {
			
			if ((DFA.accepting.has(i) && DFA.accepting.has(j)) || (!DFA.accepting.has(i) && !DFA.accepting.has(j)))
				equivalent[i][j] = true;
			else
				equivalent[i][j] = false;
		}
	}
	while (true) {
		var marked = false; 
		for (var i = 0; i < DFA.states; i++) {
			for (var j = i + 1; j < DFA.states; j++) {
				if (equivalent[i][j]) {
					DFA.alphabet.forEach(function (symbol) {
						if (!equivalent[i][j])
							return;
						var a = DFA.edges[i][symbol].values().next().value;
						var b = DFA.edges[j][symbol].values().next().value;
						if (!equivalent[Math.min(a, b)][Math.max(a, b)]) {
							equivalent[i][j] = false;
							marked = true;
						}
					})
				}
			}
		}
		if (!marked) 
			break;
	}

	var DFAm = {
		alphabet: new Set(DFA.alphabet),         
		states: 0,                      				
		edges: [],                               
		outgoing: [],      											 
		incoming: [],														 
		accepting: new Set(),         					 
		statescor: []
	}

	var taken = [];
	for (var i = 0; i < DFA.states; i++) {
		if (taken.includes(i)) 
			continue;
		if (DFA.accepting.has(i))
			DFAm.accepting.add(DFAm.states);
		DFAm.statescor[DFAm.states] = [];
		for (var j = i; j < DFA.states; j++) {
			if (equivalent[i][j]) {
				DFAm.statescor[DFAm.states].push(j);
				taken.push(j);
			}
		}
		if (DFAm.statescor[DFAm.states].includes(DFA.start))
			DFAm.start = DFAm.states; 
		DFAm.states++;
	}

	for (var i = 0; i < DFAm.states; i++) { 
		DFAm.alphabet.forEach(function (symbol) {
			var toOld = DFA.edges[DFAm.statescor[i][0]][symbol].values().next().value;
			var toNew;
			for (var j = 0; j < DFAm.states; j++) {
				if (DFAm.statescor[j].includes(toOld)) {
					toNew = j;
					break;
				}
			}
			addTransition(DFAm, i, toNew, symbol);
		})
	}
	return DFAm;
}



function generateAutomata(regex) { 
	instance = {};
	instance.NFAl = RedundantStates(constructNFAe(parseRegex(regex_global)));
	instance.NFATransition = TransitionsRemove(deepCopyAutomaton(instance.NFAl));
	instance.NFA = eliminateUnreachable(deepCopyAutomaton(instance.NFATransition), instance.NFATransition);
	instance.DFA = subsetConstruction(instance.NFA);
	instance.DFAm = minimizeDFA(instance.DFA);
	generateStrings(instance);
	instance.FAobj = [];
	instance.FAstrings = [];
}

function generateStrings(instance) { 
	for (var FA of [instance.NFAl, instance.NFA, instance.DFA, instance.DFAm]) {
		FA.examplestrings = [];
		for (var i = 0; i < FA.states; i++)
			FA.examplestrings[i] = [];
		FA.examplestrings[FA.start].push(""); 
		var indexes = [];
		indexes[FA.start] = 0;
		nextStrings(FA, [FA.start], indexes);
	}
}

function nextStrings(FA, states, startingindexes) {
	var oldlength = [];
	for (var i = 0; i < FA.states; i++)
		oldlength[i] = FA.examplestrings[i].length;
	for (var state of states) {
		for (var i = startingindexes[state]; i < oldlength[state]; i++) {
			for (var symbol in FA.edges[state]) {
				if (FA.edges[state][symbol] == undefined)
					continue;
				FA.edges[state][symbol].forEach(function (to) {
					if (FA.examplestrings[to].length == 25) 
						return;
					if (symbol != '0' && !FA.examplestrings[to].includes(FA.examplestrings[state][i] + symbol))
						FA.examplestrings[to].push(FA.examplestrings[state][i] + symbol);
					else if (symbol == '0' && !FA.examplestrings[to].includes(FA.examplestrings[state][i]))
						FA.examplestrings[to].push(FA.examplestrings[state][i]);
				})
			}
		}
	}
	var newstates = []; 
	for (var i = 0; i < FA.states; i++) {
		if (FA.examplestrings[i].length > oldlength[i]) 
			newstates.push(i);
	}
	if (newstates.length == 0) { 
		return;
	}
	nextStrings(FA, newstates, oldlength);
}

function stringMatches(DFA, string) { 
	var passed = [DFA.start];
	var cur = DFA.start;
	for (var i = 0; i < string.length; i++) {
		cur = DFA.edges[cur][string[i]].values().next().value;
		passed.push(cur);
	}
	return { "matched": DFA.accepting.has(cur), "passed": passed };
}

function addTransition(FA, from, to, symbol) {
	if (FA.edges[from] == undefined)
		FA.edges[from] = {};
	if (FA.edges[from][symbol] == undefined)
		FA.edges[from][symbol] = new Set([to]);
	else {
		if (FA.edges[from][symbol].has(to))
			return false; 
		FA.edges[from][symbol].add(to);
	}
	if (FA.outgoing[from] == undefined)
		FA.outgoing[from] = 1;
	else
		FA.outgoing[from]++;
	if (FA.incoming[to] == undefined)
		FA.incoming[to] = 1;
	else
		FA.incoming[to]++;
	return true;
}

function removeTransition(FA, from, to, symbol) {
	if (FA.edges[from][symbol].has(to)) {
		FA.outgoing[from]--;
		FA.incoming[to]--;
		FA.edges[from][symbol].delete(to);
	}
}

function removeState(FA, state) {
	if (FA.edges[state] != undefined) {
		for (var symbol in FA.edges[state]) {
			FA.edges[state][symbol].forEach(function (val) {
				removeTransition(FA, state, val, symbol);
			})
		}
	}

	
	for (var i = 0; i < FA.states; i++) {
		if (FA.edges[i] == undefined)
			continue;
		for (var symbol in FA.edges[i]) {
			FA.edges[i][symbol].forEach(function (val) {
				if (val == state)
					removeTransition(FA, i, state, symbol);
			})
		}
		for (var symbol in FA.edges[i]) {
			var newSet = new Set([]);
			FA.edges[i][symbol].forEach(function (value) {
				if (value >= state)
					newSet.add(value - 1);
				else
					newSet.add(value);
			});
			FA.edges[i][symbol] = newSet;
		}
	}
	if (FA.start >= state)
		FA.start--;
	var newaccepting = new Set([]);
	var it = FA.accepting.values();
	for (var val = it.next().value; val !== undefined; val = it.next().value) {
		if (val >= state)
			newaccepting.add(val - 1);
		else
			newaccepting.add(val);
	}
	FA.accepting = newaccepting;
	for (var i = state; i < FA.states; i++) {
		FA.edges[i] = FA.edges[i + 1];
		FA.outgoing[i] = FA.outgoing[i + 1];
		FA.incoming[i] = FA.incoming[i + 1];
	}
	FA.states--;
}

function deepCopyAutomaton(FA) {
	var copy = {
		alphabet: new Set(FA.alphabet),         
		states: FA.states,                      
		start: FA.start,                       
		edges: [],                              
		outgoing: Array.from(FA.outgoing),     
		incoming: Array.from(FA.incoming),      
		accepting: new Set(FA.accepting)       
	}
	for (var i = 0; i < FA.states; i++) {
		if (FA.edges[i] != undefined) {
			copy.edges[i] = {};
			for (var symbol in FA.edges[i]) {
				copy.edges[i][symbol] = new Set(FA.edges[i][symbol]);
			}
		}
	}
	return copy;
}

function SetHasArray(set, array) { 
	var found = false;
	set.forEach(function (val) {
		if (!found) {
			for (var i = 0; i < array.length; i++) {
				if (array[i] != val[i])
					return;
			}
			found = true;
		}
	})
	return found;
}

function ArrayHasArray(array, sub) { 
	for (var i = 0; i < array.length; i++) {
		if (ArrayEquals(array[i], sub)) {
			return i;
		}
	}
	return -1;
}

function ArrayEquals(arr1, arr2) { 
	if (arr1.length != arr2.length)
		return false;
	for (var i = 0; i < arr1.length; i++)
		if (arr1[i] != arr2[i])
			return false;
	return true;
}

function parseRegex(stringo) {
	var stream = {
		string: stringo,
		pos: 0,
		cur: (function () { return this.string[this.pos]; }),
		done: (function () { return this.pos == this.string.length; })
	};
	try {
		var tree = parseExpr(stream);
		if (!stream.done())
			throw "Non-empty stream";
		console.log(tree);
		return tree;
	}
	catch (err) {
		return -1;
	}
}

function parseExpr(stream) {
	var terms = []
	while (!stream.done()) {
		terms.push(parseTerm(stream));
		if (!stream.done() && stream.cur() == '|')
			stream.pos++;
		else
			break;
	}
	if (terms.length == 0)
		throw "Empty expression";
	else if (terms.length == 1)
		return terms[0];
	else {
		return {
			type: "or",
			value: terms
		}
	}
}

function parseTerm(stream) {
	var concats = []
	while (!stream.done()) {
		var concat = parseConcat(stream);
		if (concat != undefined) {
			if (concat.length == 2) { 
				concats.push(concat[0]);
				concats.push(concat[1]);
			}
			else {
				concats.push(concat);
			}
		}
		else
			break;
	}
	if (concats.length == 0)
		throw "Empty term";
	else if (concats.length == 1)
		return concats[0];
	else {
		return {
			type: "concat",
			value: concats
		}
	}
}

function parseConcat(stream) {
	var atom = parseAtom(stream);
	if (atom != undefined && !stream.done() && stream.cur() == "*") {
		stream.pos++;
		return {
			type: "star",
			value: atom
		}
	}
	else if (atom != undefined && !stream.done() && stream.cur() == "+") {
		stream.pos++;
		return [ 
			atom, {
				type: "star",
				value: atom
			}
		]
	}
	else {
		return atom;
	}
}

function parseAtom(stream) {
	if (stream.done())
		throw "Missing atom";
	else if (stream.cur().toUpperCase() != stream.cur().toLowerCase()) { 
		stream.pos++;
		return {
			type: "letter",
			value: stream.string[stream.pos - 1]
		}
	}
	else if (stream.cur() == '0') {
		stream.pos++;
		return {
			type: "lambda",
			value: undefined
		}
	}
	else if (stream.cur() == '(') {
		stream.pos++;
		var expr = parseExpr(stream);
		if (!stream.done() && stream.cur() == ')') {
			stream.pos++;
			return expr;
		}
		else {
			throw "Missing )"
		}
	}
	else {
		return undefined;
	}
}