Search

Foundations of formal languages, as subfield of theoretical computer science, are part of typical upper secondary education curricula. There is very little research on the potential difficulties that students at this level have with this subject. In this paper, we report on an exploratory study of errors in formal languages among upper secondary education students. We collect the data by posing exercises in an intelligent tutoring system and analyzing student input. Our results suggest a) instances of non-functional understanding of concepts such as the empty word or a grammar as a substitution system; b) strategic problems such as lack of foresight when deriving a word or confounding formal specifications with real-world knowledge on certain aspects; and c) various syntactic problems. These findings can serve as a starting point for a broader understanding of how and why students struggle with this topic.

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.

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, and report on our experiences using the material in a large introductory course on theoretical computer science., Comment: Fixed a typo compared to last version; 6 pages + references, including one page of screenshots; accepted at SIGCSE TS 2025

The Iltis project provides an interactive, web-based system for teaching the foundations of formal methods. It is designed with the objective to allow for simple inclusion of new educational tasks; to pipeline such tasks into more complex exercises; and to allow simple inclusion and cascading of feedback mechanisms. Currently, exercises for many typical automated reasoning workflows for propositional logic, modal logic, and some parts of first-order logic are covered. Recently, Iltis has reached a level of maturity where large parts of introductory logic courses can be supplemented with interactive exercises. Sample interactive course material has been designed and used in courses over the last years, many of them with more than 300 students. We invite all readers to try out Iltis: https://iltis.cs.tu-dortmund.de