Graph UI documentation

Re: Graph UI documentation

por Walter Guttmann -
Número de respuestas: 1

An example would be: given a non-deterministic finite automaton, construct a deterministic one that accepts the same language. The expected automaton is drawn as a labelled graph, just as it would be on paper. You can get ideas for automata/grammar questions from tools such as Exorciser https://www.swisseduc.ch/compscience/exorciser/index.html and JFLAP http://www.jflap.org/

The question author provides the correct answer (also by drawing a graph). A student's answer is compared against that. As you suggest, you can test all strings up to a certain length and/or some longer, random strings. If you find a string that is not correctly handled, it can be given to the student as feedback. For finite automata, there are decision procedures which can determine the correctness without testing any strings, but in practice testing is enough as there are usually short counterexamples and having these is useful for students to correct their answers. Also the testing method extends to more general automata such as pushdown automata or Turing machines whose equivalence is undecidable.

This method has been applied to other formalisms such as grammars or regular expressions (these don't need a graphical input). For grammars, you can generate all strings up to a certain length in the language generated by the student's grammar and compare them with the language generated by the correct grammar. The method can be applied to any formalism for which you can create a parser for the students' answers and an automated testing/verification procedure.

En respuesta a Walter Guttmann

Re: Graph UI documentation

por Andreas Siebel -
If someone wants to create a Finite-State-Automata-Question: I created a DFA-Validation with this library:


Here is my code:

  import json
from automata.fa.dfa import DFA
import automata

student_answer = """{{ STUDENT_ANSWER | e('py') }}"""
SEPARATOR = "##"

error_count = 0
def error(s):
    global error_count
    print(s)
    error_count += 1

class ValidationError(Exception):
    pass

try:
    graph_rep = json.loads(student_answer)
    node_id_to_name_map = {}
    for i, node in enumerate(graph_rep['nodes']):
        node_id_to_name_map[i] = node[0] if node[0] != '' else ('#' + str(i))
    edges = graph_rep['edges']
    nodes = [ node[0] for node in graph_rep['nodes'] if node[0] != "" ]
    end_nodes = [ node[0] for node in graph_rep['nodes'] if node[0] != "" and node[1] == True]
    labels = [ edge[2] for edge in graph_rep['edges'] if edge[2] != ""]
    graph = {}
    
    start_nodes = set()
    for node_id, node_name in sorted(node_id_to_name_map.items()):
        edges = dict()
        for source, target, edge_label in graph_rep['edges']:
            if source == node_id:
                edges[edge_label] = node_id_to_name_map[target]
            if source == -1:
                start_nodes.add(node_id_to_name_map[target])
        graph[node_name] = edges
    if len(start_nodes) > 1:
        raise ValidationError("Too many initial states")
    dfa = DFA(
        states= set(nodes),
        input_symbols=set(labels),
        transitions=graph,
        initial_state=start_nodes.pop(),
        final_states=set(end_nodes)
    )


except json.JSONDecodeError as e:
    raise Exception("Oops. Illegal graph received (exception {}). Please report (unless you did something silly yourself)".format(e))
except automata.base.exceptions.MissingStateError as e:
    print("Validation Error:" + str(e))
except ValidationError as e:
    print("Validation Error:" + str(e))    
    
{% for TEST in TESTCASES %}
if dfa.accepts_input("{{ TEST.stdin }}"):
    print(True)
else:
    print(False)
    
{{ TEST.extra }}
{% if not loop.last %}
print(SEPARATOR)
{% endif %}
{% endfor %}
  @17943918#@>