Module: compute

Methods

(static) closure(graph, cur_states) → {Set.<string>}

compute the set of closure of current states (in-place and returns)
Parameters:
Name Type Description
graph Object the graph containing the cur_states
cur_states Set.<string> current states the machine is in
Source:
Returns:
the closure of cur_states
Type
Set.<string>

(static) compute_alphabet()

given a graph and its input, compute the input alphabet
Source:

(static) contains_final(graph, cur_states) → {boolean}

checks if the set of states provided contains a final state
Parameters:
Name Type Description
graph Object the graph containing the cur_states
cur_states Set.<string> the set of current states we want to check if any is a final state
Source:
Returns:
true iff some state in cur_states is a final state
Type
boolean

(static) edge_has_equiv_edge_in_graph(graph, edge) → {boolean}

computes if the edge is the same as another one already in graph up to graphical representation
Parameters:
Name Type Description
graph Object
edge Object
Source:
Returns:
true iff edge in graph
Type
boolean

(static) edge_in_graph(graph, edge) → {boolean}

computes if the edge IS already in graph
Parameters:
Name Type Description
graph Object
edge Object
Source:
Returns:
true iff edge in graph
Type
boolean

(static) find_start(graph) → {string}

finds the start vertex
Parameters:
Name Type Description
graph Object the graph whose starting vertex is to be computed
Source:
Returns:
the start of the graph, null of graph empty
Type
string

(static) is_DFA()

given an NFA, check if it is in fact deterministic
Source:

(static) mealy_step(graph, cur_state, symbol) → {Object}

a single step of the NFA running algorithm
Parameters:
Name Type Description
graph Object the Mealy machine of interest
cur_state string current state of the machine
symbol string the transition symbol
Source:
Returns:
the output of the transition and the next state
Type
Object

(static) NFA_step(graph, cur_states, symbol) → {Set.<string>}

a single step of the NFA running algorithm
Parameters:
Name Type Description
graph Object the NFA of interest
cur_states Set.<string> all possible states the machine is in
symbol string the transition symbol
Source:
Returns:
a new set of states after the transition
Type
Set.<string>

(static) run_input(graph, machine_type, input, interactive) → {Iterable}

determines whether the machine is PDA or normal NFA and checks if the input is accepted
Parameters:
Name Type Description
graph Object machine graph
machine_type string type of machine the graph represents
input string input string
interactive boolean whether to step through and highlight the computation
Source:
Returns:
return a generator that if noninteractive, evaluates to the final accept/reject immediately in one step if interactive, evaluates step by step with highlight
Type
Iterable

(generator, inner) BFS_step(graph, v, remaining_input, allowed_depth) → {Iterable}

step through the the computation of PDA with BFS
Parameters:
Name Type Default Description
graph Object machine graph
v string starting vertex
remaining_input Array.<string> input string split into char array
allowed_depth int 64 the computation will halt and return false if the BFS tree is deeper than this
Source:
Returns:
a generator that evaluates to true iff the input is accepted by the machine
Type
Iterable

(inner) config_to_vertices(cur_configs)

Extract a list of vertices from a map of configurations
Parameters:
Name Type Description
cur_configs Map.<string, Array> a map of whose values are [vertex_name, stack, remaining_input]
Source:
Returns:
Set a set of vertex names

(inner) PDA_closure(graph, cur_configs)

Compute the (almost) closure of PDA states stored inside the queue q and add them to the queue Note that we only evaluate all the epsilon transitions once to speed up computation
Parameters:
Name Type Description
graph Object
cur_configs Map.<string, Array> an array of configurations [vertex_name, stack, remaining_input] we package it in a set to deduplicate
Source:

(generator, inner) run_input_Mealy(graph, input, interactive) → {Iterable}

check if the input is accepted
Parameters:
Name Type Description
graph Object machine graph
input string input string
interactive boolean whether to show the computation step by step
Source:
Returns:
a generator that evaluates to the final output of the machine
Type
Iterable

(generator, inner) run_input_NFA(graph, input) → {Iterable}

check if the input is accepted
Parameters:
Name Type Description
graph Object machine graph
input string input string
Source:
Returns:
a generator that evaluates to true iff the input is accepted by the machine
Type
Iterable

(inner) run_input_PDA(graph, input, interactive) → {Iterable}

check if the input is accepted
Parameters:
Name Type Description
graph Object machine graph
input string input string
interactive boolean whether to show the computation step by step
Source:
Returns:
a generator that evaluates to true iff the input is accepted by the machine
Type
Iterable

(generator, inner) run_input_Turing(graph, input, allowed_steps) → {Iterable}

check if the input is accepted
Parameters:
Name Type Default Description
graph Object machine graph
input string input string
allowed_steps int 512 the computation will halt and return false if the step limit is reached
Source:
Returns:
a generator that evaluates to true iff the input is accepted by the machine
Type
Iterable