-
Notifications
You must be signed in to change notification settings - Fork 0
A Sample Assignment, Submission and Solution Sets
Theory Assistant was written as a tool to aid instructors and instructors' assistants in administering courses in the subject of Formal Languages and Finite Automata, specifically to provide an API and framework to assist in the automated evaluation of exercises in the subject. A "typical" assignment, consisting of four exercises, is outlined on this page. Sample submission and solution sets for the hypothetical assignment have been implemented and provided in this repo, and they are also described in this page.
This autograder is written to evaluate an assignment which would typically be assigned to students in an introductory course on formal languages and automata. The exercises in this assignment come from the text Introduction to the Theory of Computation; 3ed, by Michael Sipser; they are exercises 1.4.a 1.4.c, 1.5.c, and 1.5.d. Here is the assignment:
- exercise 1.4.a : the set of all strings that have at least three a's and at least two b's.
- exercise 1.4.c : the set of all strings that have at an even number of a's and one or two b's.
- exercise 1.5.c : the set of all strings that contain neither the substring ab nor the substring ba
- exercise 1.5.d : all strings which are not in the language a*b*
Each of the above languages is a regular language, and as such there is a DFA which recognizes each of them. The DFA which recognizes each of the languages can be described in the GrafState syntax, and a Parser object will be capable of parsing those descriptions for evaluation by the TheoryAssistant. To grade this assignment with an autograder written with the TheoryAssistant, a student would be asked to provide a submission consisting of a tarball of four files, one file describing (in GrafState syntax) a machine which recognizes one of the above languages. A sample (extracted) submission is included in this repo. It should be noted that:
-
The sample submission for exercise 1.4a contains a machine description syntax error, in that the transition function description
d(A0,a)=B5is invalid since the stateB5is not defined as a member of the set of states. -
There is no submission for exercise 1.5d.
-
The naming convention for the directory structure of the submission tarball is entirely arbitrary and can be altered ad hoc by any instructor / assistant.
The first two submission errors are toy examples of submission errors likely to be encountered in a submission for an assignment from a student, and both are gracefully handled in the autograder implementation.
A solution set for this assignment has also been provided in this repo. In fact, two solution sets have bee provided. Both solutions are valid, and the difference between the two solution sets is explained below.
The first solution set can be found in the SampleGrader/ directory at SampleGrader/data/solutions1/. A machine which recognizes each of the languages described in exercises 1.4a, 1.4c, 1.5c, and 1.5d is implemented in a file in the above directory with the same name. This solution set requires slightly more work to implement than the second solution set, however its accompanying autograder is slightly easier to write and understand than the autograder written for the second solution set.
The second solution set can be found in the SampleGrader/ directory at SampleGrader/data/solutions2/. The machines which can be used to generate the solutions for the assignment are implemented in this directory. The languages in the assignment are all languages which are more easily understood as either the union of two simpler languages or the complement of a simpler language; those simpler languages are all implemented in the solutions2/ directory.
From here take a look at the page describing the importance of a naming convention, the use of JAR files to include the TheoryAssistant package in an autograder project, and the sample rubric for the sample assignment.