# PCASTLI version 3.4 auto = names("S", "Sigma", "Gamma", "T", "iota", "F") # States auto.S = array(1, 2, 3, 4) # Alphabet auto.Sigma = array("a", "b") # Stack Alphabet auto.Gamma = array("a", "b", "#") # Transitions (non self-modifying) #make_trans = function(init_state, input_symbol, popped_symbol, new_state, pushed_symbol) #{ # transition = names("init_state", "input_symbol", "popped_symbol", "new_state", "pushed_symbol") # transition.init_state = init_state # transition.input_symbol = input_symbol # transition.popped_symbol = popped_symbol # transition.new_state = new_state # transition.pushed_symbol = pushed_symbol # transition #} source("gen-trans-func.astl") make_trans = make_trans_func(array("init_state", "input_symbol", "popped_symbol", "new_state", "pushed_symbol")) auto.T = array( make_trans(1, "", "", 2, "#"), make_trans(2, "a", "", 2, "a"), make_trans(2, "b", "a", 3, ""), make_trans(3, "b", "a", 3, ""), make_trans(3, "", "#", 4, "") ) # Start state auto.iota = 1 # Set of accept states auto.F = array(1, 4) run_automaton = function(auto, string) { state = auto.iota stack = names("data", "push", "pop", "peek") stack.data = list() stack.push = function(el) insert(data, list(el), 0) stack.pop = function() remove(data, 0) stack.peek = function() { if (length(data) > 0) return(data[0]) return("") } sl = strlen(string) TLen = length(auto.T) i = 0 found_trans = 1 while (found_trans && i < sl) { j = 0 found_trans = 0 while (!found_trans && j < TLen) { if (state == auto.T[j].init_state && (auto.T[j].input_symbol == "" || auto.T[j].input_symbol[0] == string[i]) && (auto.T[j].popped_symbol == "" || auto.T[j].popped_symbol == stack.peek())) { found_trans = 1 state = auto.T[j].new_state if (auto.T[j].popped_symbol != "") stack.pop() if (auto.T[j].pushed_symbol != "") stack.push(auto.T[j].pushed_symbol) } else { j++ } } if (found_trans) { if (auto.T[j].input_symbol != "") i++ } } if (i == sl) { # checking if current state is final i = 0 found_final = 0 nb_finals = length(auto.F) while (i < nb_finals && !found_final) { if (state == auto.F[i]) found_final = 1 i++ } if (found_final) { print("accepted") return() } # trying to reach a final state by manipulating the stack found_trans = 1 while (found_trans) { j = 0 found_trans = 0 while (!found_trans && j < TLen) { if (state == auto.T[j].init_state && auto.T[j].input_symbol == "" && (auto.T[j].popped_symbol == "" || auto.T[j].popped_symbol == stack.peek())) { found_trans = 1 state = auto.T[j].new_state if (auto.T[j].popped_symbol != "") stack.pop() if (auto.T[j].pushed_symbol != "") stack.push(auto.T[j].pushed_symbol) } j++ } } } else { print("refused") return() } i = 0 found_final = 0 nb_finals = length(auto.F) while (i < nb_finals && !found_final) { if (state == auto.F[i]) found_final = 1 i++ } if (found_final) print("accepted") else print("refused") } run_automaton(auto, "") run_automaton(auto, "aabb") run_automaton(auto, "aab") run_automaton(auto, "aabbb")