Computer science students often struggle with abstract theoretical concepts, particularly in introductory courses on theoretical computer science. One such challenge is understanding context-free languages and their various representations. In this study we investigate factors that influence the difficulty of constructing context-free grammars and pushdown automata for context-free languages. We propose two potential difficulty generating factors targeting how a language is presented to students: representation in natural language and as a verbose set notation. Furthermore, we propose two factors targeting the structure of the given context-free language: nesting of constructs and insertion of multiplicities. We conducted a controlled experiment using within-subject randomization in an interactive learning system, testing the proposed difficulty factors for constructing context-free grammars and pushdown automata. Our results suggest that three of the four factors significantly influence students' objective performance in solving exercises for constructing context-free grammars, while students' perceived difficulties only partly align with the objective performance measures. The findings for pushdown automata tasks differed markedly from those for context-free grammar tasks. Our variations either had negligible effects or, in some cases, even reduced difficulty. Thus, no robust statistical conclusions can be made for pushdown automata tasks. The results lay foundations for learning systems that adaptively choose appropriate exercises for individual students.

Computational reductions are an important and powerful concept in computer science. However, they are difficult for many students to grasp. In this paper, we outline a concept for how the learning of reductions can be supported by educational support systems. We present an implementation of the concept within such a system, concrete web-based and interactive learning material for reductions between graph-based problems, and report on our experiences using the material in a large introductory course on theoretical computer science.

We propose a scalable framework for deciding, proving, and explaining (in-)equivalence of context-free grammars. We present an implementation of the framework and evaluate it on large data sets collected within educational support systems. Even though the equivalence problem for context-free languages is undecidable in general, the framework is able to handle a large portion of these datasets. It introduces and combines techniques from several areas, such as an abstract grammar transformation language to identify equivalent grammars as well as sufficiently similar inequivalent grammars, theory-based comparison algorithms for a large class of context-free languages, and a graph-theory-inspired grammar canonization that allows to efficiently identify isomorphic grammars.

In this paper we advocate the study of misconceptions in the formal methods domain by integrating quantitative and qualitative methods. In this domain, so far, misconceptions have mostly been studied with qualitative methods, typically via interviews with less than 20 subjects. We discuss workflows for (1) determining the commonness of qualitatively established misconceptions by quantitative means; and for (2) the initial discovery of misconceptions by quantitative methods followed by qualitative assessments.

Iltis is an interactive, web-based system for teaching logic. It is designed to provide immediate and comprehensive feedback for exercises covering various aspects of the reasoning workflow. This poster presentation reports on new exercises and feedback mechanisms for modal and first-order logic.