// the five tuples
const Q = states = new Set(['q1', 'q2', 'q3', 'q4'])
const Sigma = alphabet = new Set(['0', '1'])
const delta = transitionFunction = (state, symbol) => {
const table = {
'q1': {
'0': new Set(['q1']),
'1': new Set(['q1', 'q2']),
'e': new Set()
},
'q2': {
'0': new Set(['q3']),
'1': new Set(),
'e': new Set(['q3'])
},
'q3': {
'0': new Set(),
'1': new Set(['q4']),
'e': new Set()
},
'q4': {
'0': new Set(['q4']),
'1': new Set(['q4']),
'e': new Set()
}
}
return table[state][symbol]
}
const q0 = startState = 'q1'
const F = finalStates = new Set(['q4'])
function union(setA, setB) {
var _union = new Set(setA);
for (var elem of setB) {
_union.add(elem);
}
return _union;
}
const check = (string) => {
let arr = string.split("")
let currStates = new Set([q0])
for (let i = 0; i < arr.length; i++ ) {
let _currStates = new Set()
for (let state of currStates) {
_currStates = union(_currStates, delta(state, arr[i]))
}
currStates = _currStates
}
for (let state of currStates) {
if (F.has(state)) return 'accept'
}
return 'reject'
}
check('100')
check('1010')
check('010110')
no comments
sign in to comment