The material taught in a Formal languages course is mathematical in nature and requires students to practice proofs and algorithms to understand the content. Traditional Formal Languages textbooks are heavy on prose, and homework typically consists of solving many paper exercises. Students need to read a signi cant amount of text and do practice problems by hand to achieve understanding. Electronic textbooks have many useful methods to display the content to students. However, unless carefully designed, students abuse these methods to earn grades without studying the content carefully. Inspired by the principles of the Programmed Instruction (PI) teaching method, we seek to develop a new Formal Languages eTextbook capable of conveying Formal Languages concepts more intuitively. The PI approach has students read a little, ideally a sentence or a paragraph, and then answer a question or complete an exercise related to that information. Based on the question response, students are permitted to continue on to other frames of information, or must retry to solve the exercise. Our goal is to present all algorithms using algorithm visualizations and to produce auto-graded exercises to let students demonstrate understanding. To evaluate the pedagogical e ectiveness of our new eTextbook, we plan to conduct time and performance evaluations across three o erings of the course CS4114 Formal Languages and Automata at Virginia Tech. The time spent by students looking at instructional content with text and visualizations will be compared with time spent using PI frames to determine levels of student engagement.
In this paper, we discuss how to help students in a Formal Languages course to better engage, understand, and practice the course content. We do this through new implementations of an old pedagogy called Programmed Instruction. We argue for why this is superior for the type of material taught in Formal Languages than is used in traditional textbooks.
In 1953, BF Skinner went to his daughter's school to ask about her progress [
PI and similar teaching machines were once leading areas of research and
development. Much of this research was conducted during the 1950s and died
out in the early 1970s. During this period, PI research revolved around
addressing instructional e ectiveness, learner pacing, reinforcement strategies, and
long-term e ects [
The Personalized System of Instruction (PSI, or Keller Plan) became widely
used during the 1970s and 1980s [
Formal Languages is a core course in Computer Science Theory. It often
includes topics on computability theory, complexity theory, state machines, and
Turing machines. Formal Languages topics are applied in a number of
realworld applications like compiler architectures and pattern matching. However,
the material is mathematical and theoretical, requiring students to practice many
di cult skills. The course uses a lot of models such as nite automata,
pushdown automata, and Turing machines. There are algorithms associated with each
model that students must learn to apply. Currently, many books and instructors
use simulators to help students understand the models and apply the
associated algorithms. One state-of-the-art simulator is the Java Formal Languages
and Automata Package (JFLAP) [
We observe that often students read Formal Languages proofs and get nothing from them, yet continue on with their reading by skipping this material. We want to design an educational system that challenges students to engage at every step in the course. We seek to help students form a better understanding of the concepts taught in Formal Languages by forcing students to demonstrate their understanding at small increments. We do this by adopting PI principles. We seek to create an eTextbook will be made up of small frames. Each one includes a challenge question or problem that must be completed before they can continue to the next frame. We hypothesize that following this approach will increase student engagement, which will lead to a better understanding of the course content.
The OpenDSA project [
In the rest of this paper, we present our design and prototype implementation and evaluation plans for a new eTextbook to teach Formal Languages using the PI technique. The heart of the implementation is a modi ed form of JSAV slideshows built on the frames concept. A student will see a series of slides (the frames). Frames will add a constraint on the \next" button that normally appears in the slideshows. Students will not be able to click on the \next" button until they satisfy a pre-determined criterion for each frame, such as selecting the correct answer or applying a speci c algorithm step on a given model.
By implementing the new eTextbook, we believe that students will gain a better intuition about Formal Languages content, which is hard to grasp when relying merely on textual discussion and static gures. Heavy use of interactive visualizations, as inspired by JFLAP, combined with the PI pedagogy of asking frequent questions, will increase student interaction, engagement, and practice with course content. Also, the eTextbook will keep track of students' click streams, scores, problem attempts, and time spent on each frame. These data will be used to improve the system, and to prove (or disprove) the e ectiveness of the system in teaching Formal Languages.
Evaluating the pedagogical e ectiveness of the new eTextbook is a challenge.
It is a challenging task to measure student learning gains, especially if this gain is
a result of technological interventions [
We also seek to create guidelines for other researchers who might seek to use PI principles to create other eTextbooks. The CS community knows how to design and implement eTextbooks, but has little experience with PI teaching techniques. Accordingly, a clear set of guidelines should be developed to motivate more work in developing this type of eTextbook. 2
According to [
{ A typical PI sequence consists of an introduction, diagnostic section,
theory section, teaching, testing section, practice section, and nally review
or summary to reinforce the concepts addressed.
{ Pragmatic approach. The frame is based on the logical sequence of the
material. The PI materials must simply address all necessary information
and components.
{ RULES and EXAMPLES (RULEG) system [
{ The information that the student should learn. { Incentive to obtain the targeted response. In other words, the frame should contain a question that leads the student to grasp the information. { Response that lets the student indicate that they have gained the desired knowledge. { Other materials that make the frame readable and understandable, like visualizations.
Another important frame component is the method that is used to present
the information to the student (the prompt). The prompt plus some of the
previously acquired learning will make students able to answer the questions
in the frames correctly. Prompts can be formal or thematic [
Another critical design consideration for frames is the question type. Questions are necessary and help students to acquire the intended learning outcomes. Many di erent types of questions can be used in frames like multiple choice, true or false, and labeling, name a few. 7. Evaluation and Revision. The nal step is to evaluate the programmed product and revise it. The primary source of evaluation is learner feedback on the product. But learners are unable to judge some factors, like possible errors in content, accuracy, appropriateness, and relevance. Thus there should be external reviewers ( eld experts) to review the initial product. 3 3.1
We are building our eTextbook within the OpenDSA eTextbook system in three phases. In the rst phase, during Spring 2018, we used standard course materials to teach the Formal Languages course. While the \textbook" content was delivered through OpenDSA, it was largely text-based prose. We created thirteen (paper-based) homework assignments, two midterm exams, and a nal exam. To construct the control data, we collected all student results from the homework assignments and exams.
In Spring 2019, (and planned for Fall 2019) students use the Phase 2 eTextbook. This builds on the existing OpenDSA eTextbook materials from Spring 2018 to include many visualizations for the various algorithms. We are adding to our collection of online exercises, and are gradually converting JFLAP to an integrated equivalent within OpenDSA (that we refer to as OpenFLAP). We also kept the same paper homework assignments and exam questions, collecting grades from them to use as a direct comparison with the Spring 2018 cohort from Phase 1.
The third phase eTextbook is planned to be available in Spring 2020. By then we hope to have converted the textbook content to be delivered as PI frames. The eTextbook will consist of a set of modules. Each module will be a set of frames. We will use the same homework and exams as in Phases 1 and 2.
By collecting meaningful data from these three phases, we can compare the impact of each phase on knowledge gain. For instance, we can compare Phase 1 and Phase 2 data to study the impact of evolving visualizations from prose. Comparing Phase 1 and Phase 3 outcomes lets us study the e ectiveness of a PI eTextbook on student gains. Comparing Phase 2 and Phase 3 allows us to assess the relative impact of visualizations versus PI frames.
Another type of data we can collect is the student engagement with the course materials. In Phase 2 and Phase 3, we can record the time spent by students to nish each slideshow. In Phase 3, we can record more information like the number of attempts to solve each frame-related question, and the time spent by students to solve each question. These data will constitute the time evaluation. Based on the results of time evaluation, we can conclude whether using PI materials lead to an increase in student engagement and interaction with the course content or not.
During our phases, di erent instructors, teaching assistants, and students will be involved, which may a ect the quality of our results. For example, the instructor of the course in Phase 1 is di erent from the instructor for Phase 2. We expect the Phase 2 and Phase 3 instructors to be the same. The teaching assistants will be di erent for each instance of the course. These di erences will a ect some factors in the study, such as course presentation and explanation, homework, and exam grading.
To decrease the e ects of variability, we are taking the following steps. { We created a uni ed rubric for all homework given to the students in Phase 1. Therefore, di erent Teaching Assistants will use the same rubric to grade students answers for homework throughout all phases. This way we will limit the variability due to di erent Teaching Assistants. In Phase 3, we will implement a number of these exercises in the form of auto-assessed exercises. { We use the same midterm and nal exams throughout all phases of the project. Using the same exams will maintain grading consistency using a uni ed rubric. In this way, we will limit the e ect of di erent graders that may yield to di erent grades on similar answers. 3.2
We have created a JavaScript framework to support PI materials delivery. Frames are visually similar to existing JSAV slideshows. OpenDSA uses reStructuredText (RST) as its content authoring system. The Sphinx compiler combines RST les with JavaScript visualizations to form HTML pages that make up the OpenDSA modules. Adding frames to book modules will be similar for content authors to adding slideshows.
We implemented the required functions to gain control over the \next slide" button to enforce students to study the frame and satisfy the criterion that will allow them to move forward. Design changes give students a di erent lookand-feel to separate them from traditional slideshows. We have completed the support infrastructure, and are starting to write the actual PI materials needed for Phase 3. Figures 1 and 2 show PI-Frames examples. 3.3
The eTextbook constitutes the main artifact for this project. It consists of a set of modules, each module consisting of a series of framesets. Each frameset presents visualizations to help the students understand a Formal Languages model, and the underlying algorithms that are applied to these models. While we have completed development of the Frames framework and the bulk of the Phase 2 book, this does not mean that the Phase 3 book will be implemented easily. We will face some challenges to complete the Phase 3 materials.
{ Converting all textual descriptions into framesets. We need to think about converting each topic in the course to be in the form of frames. Each frame has a small piece of information and an appropriate question based on that given information. This conversion can be direct in some topics, for instance describing an algorithm, but it also can be hard for other topics. { Framesets length. We need to develop the framesets to be of moderate length.
We do not want to make students feel tired from completing a frameset that is too long. { PI design decisions. There are some design decisions we have to take to produce the book. For instance, we must decide whether the framesets will be sequential or not. In each decision, there are pros and cons. { Collecting data from student usage for the new book. We need to collect appropriate data related to student time and attempts on each frame. These data will help us to identify the impact of our system on student engagement. { De ne a mechanism to help struggling students. Based on the principals of the PI teaching technique, students cannot move forward from the current frame until they successfully satisfy the associated frame criterion. Of course, we do not want a student to be stuck on any frame for too long. We need students to try again by rereading the frame or previous frames. However, what if the student can not satisfy the criterion? Or what if there is a bug that makes it impossible to move forward by \correctly" answering the question? We need to nd a mechanism that can help the students to go forward by giving the student the appropriate hints and guidance that will make the student try to satisfy the criterion again with a successful solution. These hints and guidelines will be frame speci c and must be implemented in a way that ensures that the student understands the information in order to go forward. Alternatively, there may be value in providing a bypass mechanism, but this needs to be done in a way that will avoid abuse. Our project includes creating auto-graded exercises. In the original Phase 1 course o ering, we gave thirteen homework assignments to students. Many of these exercises can be converted from paper exercises to auto-assessed exercises. Doing that will help us save the time needed to grade these exercises, will standardize the grading policies for Phase 2 and Phase 3 homework assignments, and encourage other Formal Languages instructors to use our book. This is one of the value-added features that we can gain by converting JFLAP to its OpenFLAP version, and thereby take advantage of the exercise frameworks and expertise available from the OpenDSA project.
However, we will not be able to convert all questions to auto-graded pro ciency exercises. The main reason is that many of the most valuable questions are mathematical in nature, requiring students to do things like write proofs. So while we know how to automate grading of exercises that involve constructing machines or showing the behavior of an algorithm, and we certainly can automate questions that can be cast as multiple choice or other common question formats, many important parts of the assessment process will have to be performed by human graders.
Fortunately many interesting questions can be auto-graded. We expect that many questions will be of the nature where students must create a nite state or other type of machine, similar to writing a program to solve a particular problem. Just as when writing a program, that can be auto-graded using test cases, we can auto-grade student machines by running test cases on them. To help instructors build such \pro ciency" exercises, we created a web page, with an example in Figure 3. This guides the developer when designing the exercise. The exercise generator allows the developer to easily include \unit" test cases that will determine the correctness of the student's answer. The generator will produce an HTML page that can be embedded inside an OpenDSA module.
The main bene t from this generator is that instructors can easily generate any number of exercises to their students without thinking about the grading burden. When necessary, these exercises can easily be modi ed, so developers can improve their exercises. Students will be able to test their understanding of the content by trying these exercises.
Auto-graded exercises can be integrated inside PI-Frames. Students use the framesets to understand the frame content, and prove their understanding by solving the frame question. Instructors can add auto-graded exercises in a frame. Figure 4 shows an auto-graded exercise that is displayed inside a PI-Frame. 5
OpenDSA provides infrastructure and materials to support courses in a wide variety of Computer Science-related topics. Traditionally, OpenDSA uses slideshows to explain and visualize Data Structures and Algorithms content. OpenDSA allows students to demonstrate knowledge of an algorithm by completing interactive exercises. However, static presentation of abstract, math-heavy material can be easily abused or skipped by students who quickly click through or skip the slides, or otherwise ignore the content. In general, static presentation is not an e ective way for students to learn demanding material such as is presented in a Formal Languages course. In this paper we proposed to use Programmed Instruction (PI) pedagogy. PI is based on frames, small units of text along with a question or exercise that the student must answer before continuing to the next frame. We have implemented a frame-based system, and are collecting data to analyze the e ectiveness of this approach.