Máquina AFND

by Klawztro

JavaScript

var q0 = {},
    q1 = {},
    q2 = {},
    qf = {};

q0.a = [q1,q0];
q0.b = [q0];
q1.a = [q2];
q2.b = [qf];
qf.final = true;

function eclose(state) {
    var state_list;
    
    if (typeof state.E === 'undefined') {
        return [state];
    } else {
        state_list  = eclose(state.E);
        state_list.unshift(state);        
        return state_list;
    }
    
}


function iterate(word,late_state) {
    var letter = word.shift(),
        atual_state_list = late_state[letter],
        atual_state,
        valid_word = false,
        list_size = (typeof atual_state_list !== 'undefined') ? atual_state_list.length : 0;
        cont = 0;

    
    if (typeof atual_state_list === 'undefined') {     //Machine lock. 
        console.log('Machine lock');  
        return false;
    }    
    
    
    for (; cont < list_size; cont++) {
        atual_state = atual_state_list[cont];
        
        if (word.length === 0 && atual_state.final === true) {
            return  true;
        }

        valid_word = iterate(word,atual_state);                
    }   
    return valid_word;
}


function strToArray(word) {
    var letter,
        size = word.length,
        _array = [],
        cont = 0;
    
    for (; cont < size; cont++) {
        _array.push(word.charAt(cont));
    }    
    return _array;
}


var palavra = strToArray('bbbaabbab');
alert(iterate(palavra,q0));